<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Tom on Medium]]></title>
        <description><![CDATA[Stories by Tom on Medium]]></description>
        <link>https://medium.com/@chuncaohenli?source=rss-42b8f77662ee------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*5H4EnrzsX5zqlNWDs3z3XQ.png</url>
            <title>Stories by Tom on Medium</title>
            <link>https://medium.com/@chuncaohenli?source=rss-42b8f77662ee------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 15:44:57 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@chuncaohenli/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[1227. Airplane Seat Assignment Probability]]></title>
            <link>https://medium.com/@chuncaohenli/1227-airplane-seat-assignment-probability-4784f81cafec?source=rss-42b8f77662ee------2</link>
            <guid isPermaLink="false">https://medium.com/p/4784f81cafec</guid>
            <category><![CDATA[probability]]></category>
            <category><![CDATA[math]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Tom]]></dc:creator>
            <pubDate>Mon, 19 Oct 2020 23:38:36 GMT</pubDate>
            <atom:updated>2020-10-19T23:38:36.157Z</atom:updated>
            <content:encoded><![CDATA[<p>Problem Link: <a href="https://leetcode.com/problems/airplane-seat-assignment-probability/">https://leetcode.com/problems/airplane-seat-assignment-probability/</a></p><p>We can calculate the probability P(n will seat on his/her own seat). To simplify the problem, assume that i-th customer is assigned to i-th seat</p><blockquote>P(n will seat on his/her seat) = P(1 not seat on n-th seat, 2 not seat on n-th seat, ….. (n-1) not seat on n-th seat)</blockquote><p>For 1st customer,</p><ol><li>if 1 seats on 1st seat, then 2 will pick 2nd seat, 3 will pick third one and everyone will seat on assigned seat ( P = 1/n )</li><li>if 1 seats on 2nd seat, then 2 faces the same situation as 1. 2 needs to randomly pick a seat from (n-1) seats</li><li>if 1 seats on 3rd seat, then 2 has to pick 2nd and 3 will face the same situation as 1, randomly picking a seat from (n-2) seats</li></ol><p>Now we can clearly see the patterns here. Assume that f(n) is the probability that we are looking for, when n &gt; 2,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/763/1*LWo43sJ7u9uC17FYWRT1ZQ.png" /></figure><p>when n ≤ 2,</p><ol><li>f(1) = 1</li><li>f(2) = 0.5</li></ol><p>And we can prove that f(n) == f(n-1) when n &gt; 2</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QyLfwkCK-EA3ael8EFA11Q.png" /></figure><p>So when n≥2 , f(n) is always 0.5</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4784f81cafec" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[1335. Minimum Difficulty of a Job Schedule]]></title>
            <link>https://medium.com/@chuncaohenli/1335-minimum-difficulty-of-a-job-schedule-5ee30d10a88b?source=rss-42b8f77662ee------2</link>
            <guid isPermaLink="false">https://medium.com/p/5ee30d10a88b</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[dynamic-programming]]></category>
            <category><![CDATA[dfs]]></category>
            <dc:creator><![CDATA[Tom]]></dc:creator>
            <pubDate>Thu, 13 Feb 2020 19:24:12 GMT</pubDate>
            <atom:updated>2020-02-13T19:24:12.603Z</atom:updated>
            <content:encoded><![CDATA[<p>Problem link: <a href="https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/">https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/</a></p><h3>1. Brute Force → Dynamic Programming (TLE)</h3><p>The problem is equivalent to cutting input array (list of job difficulties) into d pieces. Let’s say we have N jobs and d days, we need to choose d cutting points among N-1 job intervals. Let’s take a look at example 4:</p><pre><strong>Input:</strong> jobDifficulty = [7,1,7,1,7,1], d = 3<br><strong>Output:</strong> 15</pre><p>We have following possible cut solutions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*51wnOgK6hf09hfPVT_n6nw.png" /></figure><p>Let’s use a 2D matrix to store the biggest difficulty inside this range</p><pre>dp = [[0] * N for _ in range(N)] # N is number of tasks<br>dp[i][j] means the biggest difficulty of the task inside range[i, j]</pre><p>Each solution will use following values:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/731/1*FPpqBMjg0NhAE3nn-GW3dQ.png" /></figure><p>We can see that highlighted parts are all duplicates, which means we can store those value and reuse them for saving execution time. Sadly this solution is still not good enough. The time complexity is O(Combination(n, d))</p><h3>2. Bottom up Dynamic Programming (AC)</h3><p>TLE in solution 1 means we need to cache more intermediate results. We use 2-d array dpto store intermediate results.</p><ol><li>definition:dp[i][j] means if we want to complete first (j+1)jobs using exact (i+1)days, the minimum difficulty we can get.</li></ol><p>2. transition formula:</p><pre>dp[i][j] = min(dp[i][j], dp[i - 1][r - 1] + max(jobdifficulty[i:r+1]) for r in range(j, i - 1)</pre><p>3. initialization: for first row, dp[0][j] means we want to finish first (j+1) jobs using exactly 1 day. So we need to initialize the first row with value max(jobDifficulty[:j+1])</p><p>4. Code:</p><pre>class Solution:<br>    def minDifficulty(self, jobDifficulty: List[int], d: int) -&gt; int:<br>        n = len(jobDifficulty)<br>        if n &lt; d:<br>            return -1<br>        dp = [[0] * n] + [[float(&#39;inf&#39;)] * n for _ in range(d - 1)]<br>        dp[0][0] = jobDifficulty[0]<br>        for i in range(1, n):<br>            dp[0][i] = max(jobDifficulty[i], dp[0][i - 1])</pre><pre>for i in range(1, d):<br>            for j in range(i, n):<br>                max_r = jobDifficulty[j]<br>                for r in range(j, i - 1, -1):<br>                    max_r = max(max_r, jobDifficulty[r])<br>                    dp[i][j] = min(dp[i][j], max_r + dp[i - 1][r - 1])<br>        return dp[-1][-1]</pre><p>5. Test case:</p><p>Input</p><pre>jobDifficulty = [7, 1, 7, 1, 7, 1]<br>d = 2</pre><p>Fill in dp 2 d array</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JAcWSChPc66lzc0_aPLlnA.gif" /></figure><p>Output: 8</p><h3>3. Top down Dynamic Programming (AC)</h3><p>We can also derive top down dp solution from dfs solution.</p><pre>class Solution:<br>    def minDifficulty(self, jobDifficulty: List[int], d: int) -&gt; int:<br>        n = len(jobDifficulty)<br>        if n &lt; d:<br>            return -1</pre><pre>dp = [[None] * n for _ in range(d + 1)]</pre><pre>def dfs(d, i):<br>            if i == n and d == 0:<br>                return 0<br>            if i == n or d == 0:<br>                return -1<br>            if dp[d][i]:<br>                return dp[d][i]<br>            max_cur = jobDifficulty[i]<br>            res = float(&#39;inf&#39;)<br>            for j in range(i, n):<br>                max_cur = max(max_cur, jobDifficulty[j])<br>                val = dfs(d - 1, j + 1)<br>                if val != -1:<br>                    res = min(val + max_cur, res)<br>            dp[d][i] = res<br>            return res<br>        return dfs(d, 0)</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5ee30d10a88b" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Animated Algorithm]]></title>
            <link>https://medium.com/@chuncaohenli/animated-algorithm-a9fa339d44c?source=rss-42b8f77662ee------2</link>
            <guid isPermaLink="false">https://medium.com/p/a9fa339d44c</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[leetcode]]></category>
            <category><![CDATA[graph]]></category>
            <category><![CDATA[dijkstra]]></category>
            <dc:creator><![CDATA[Tom]]></dc:creator>
            <pubDate>Wed, 29 Jan 2020 01:55:53 GMT</pubDate>
            <atom:updated>2020-01-29T02:01:32.802Z</atom:updated>
            <content:encoded><![CDATA[<h3>Dijkstra</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OEIUvTq5lRP-ihbmRR-OIQ.gif" /></figure><p>Slides link: <a href="https://1drv.ms/p/s!Al_LW_cYFPR_wgz7DO_efcoBnR3W">https://1drv.ms/p/s!Al_LW_cYFPR_wgz7DO_efcoBnR3W</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a9fa339d44c" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>