Leetcode DP study plan list II

  1. Day 1 Basics of Dynamic Programming
  2. Day 2 One Dimensional Dynamic Programming
  3. Day 3 One Dimensional Dynamic Programming
  4. Day 4 One Dimensional Dynamic Programming
  5. Day 5 One Dimensional Dynamic Programming
  6. Day 6 One Dimensional Dynamic Programming
  7. Day 7 Dynamic Programming on String
  8. Day 8 Dynamic Programming on String
  9. Day 9 Dynamic Programming on String
  10. Day 10 Dynamic Programming on String
  11. Day 11 Dynamic Programming on String
  12. Day 12 Dynamic Programming on String
  13. Day 13 Min/Max Path Sum
  14. Day 14 Classic Dynamic Programming Problems
  15. Day 15 Memoization
  16. Day 16 Unique Paths
  17. Out of Boundary Paths
  18. Unique Binary Search Trees
  19. Day 19 Coin Change / Combination Sum
  20. Day 20 Coin Change / Combination Sum
  21. Day 21 Partition Equal Subset Sum

Leetcode DP study plan list III

  1. Day 1 Classic Dynamic Programming Problems
  2. Day 2 One Dimensional Dynamic Programming
  3. Day 3 One Dimensional Dynamic Programming
  4. Day 4 One Dimensional Dynamic Programming
  5. Day 5 Dynamic Programming on String
  6. Day 6 Dynamic Programming on String
  7. Day 7 Dynamic Programming on String

Climb Stairs / Jump Games

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Thought process

  • This is exactlly the fibonacci number question.
  • Let dp[i] be the number of ways we can get to ith step.
  • Then dp[i] = dp[i - 1] + dp[i - 2] since we can either go 1 step up from i - 1 or 2 steps up from i - 2.
def climb_stairs(n):
    current, prev = 1, 1
    for _ in range(1, n):
        current, prev = current + prev, current
    return current

746. Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Thought process:

  • Whenever we are at ith step, no matter 1 or 2 steps we move up, we have to pay the cost of cost[i].
  • So let dp[i] be the minimal cost we will pay to get to i and move on.
  • dp[i - 1] will be the min cost to get to i from 0 through stepping one step up from i - 1.
  • dp[i - 2] will be the min cost to get to i from 0 through stepping two steps up from i - 2.
  • The transition formula is: dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i].
def min_cost_climbing_stairs(cost):
    prev, curr = cost[:2]
    for i, c in enumerate(cost[2:], 2):
        prev, curr = curr, min(prev, curr) + c
    return min(prev, curr)

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Thought process:

  • Let dp[i] indicates whether we can reach the end from location i, obviously dp[-1] = True.
  • We work from right to left, mark dp[j] to be True if any of the locations we can jump to from j is True.
  • dp[0] tells us whether we can reach the end from location 0.
def jump(nums):
    n = len(nums)
    dp = [0] * len(nums)
    dp[-1] = 1

    for i in range(n - 2, -1, -1):
        step = nums[i]
        reach = min(i + step, n - 1)
        if any(dp[j] for j in range(i, reach + 1)): dp[i] = 1
    return dp[0]

Thought process:

  • The above procedure is not efficient, as we would need to check a range of values at each step. The dp table stores only binary information.
  • We can put more info in the dp table and reduce the range scan at each step.
  • Let dp[i] be the furtherest step we can get to from i, it is the maximum between dp[i - 1] and i + nums[i].
  • We pad the dp table with one 1 at the left, since we always can get to the first position.
def jump(nums):
    dp = [1] + [0] * len(nums)
    for i, num in enumerate(nums, 1):
        if i > dp[i - 1]: return False
        dp[i] = max(i + num, dp[i - 1])
    return True

Now notice the dp transition formula is just take the maximum between two quantities, one is calculated at i and one is the previous result, we can simplify the code to use constant space:

def jump(nums):
    prev = 0
    for i, num in enumerate(nums):
        if i > prev: return False
        prev = max(prev, i + num)
    return True

45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array. cEach element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps.

Thought process:

  • Let dp[i] be the number of jumps we need to get to the end.
  • We initialize everything to be infinity except 1 for the end(Since we need at least 1 jump to get to the end).
  • We populate the table from right to left.
  • The transition formula is dp[i] = min(dp[j] for j in reachable positions from j) + 1
  • dp[0] is what we need.
def jump(nums):
    n = len(nums)
    dp = [float('inf')] * len(nums)
    dp[-1] = 0
    for i in range(n - 2, -1, -1):
        step = nums[i]
        reach = min(i + step, n - 1)
        dp[i] = min(dp[i: reach + 1]) + 1
    return dp[0]

Thought process:

  • Same rational as with the Jump Game problem, we can have \(O(n)\) solution.
def jump(nums):
    dp = [0] * len(nums)
    nxt = 0
    num_steps = 0
    for i, num in enumerate(nums):
        if i > nxt:
            num_steps += 1
            nxt = dp[i - 1]
        dp[i] = max(i + num, dp[i - 1])
    return num_steps

Same rational as above, we can reduce the space usage to constant.

def jump(nums):
    prev, nxt, num_steps = 0, 0, 0
    for i, num in enumerate(nums):
        if i > prev:
            prev = nxt
            num_steps += 1
        nxt = max(nxt, i + num)
    return num_steps

Knapsack

The two dimensions of the dp table typically represents:

  • items to take.
  • capacity / target.
  • where the cell value is something like the max value we can get with the items not exceeding the capacity.
  • the solution to the question typicall be the last cell in the table.
  • depends on the problem, the 2D table may be simplified to 1D.

416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Thought process:

  • Find a partition of two subsets with equal sum is equivalent to find one subset sum up to half of the overall sum.
  • Use dp to find it out.
  • The elements in 2D table dp[i][j] means with the first i - 1 numbers from the set can I use them to sum up to j.
  • Let n be the number of integers in set and s be the sum of the set, the dp table is of size n by s // 2 + 1.
  • \(+1\) for that we padded left with 0, since we can always choose to not add anything to sum up to zero.
def can_partition(nums):
    s = sum(nums)
    if s % 2: return False
    s //= 2
    n = len(nums)
    dp = [[True] + [False] * s for _ in range(n)]
    if nums[0] <= s: dp[0][nums[0]] = True

    for i, num in enumerate(nums[1:], 1):
        for j in range(1, s + 1):
            if dp[i - 1][j]:
                dp[i][j] = True
            elif j >= num:
                dp[i][j] = dp[i - 1][j - num]
    return dp[-1][-1]

494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Thought process

  • Let \(f(i, s)\) be the number of ways we can assign symbols to make sum of first \(i\) numbers sum to \(s\). So we want return \(f(n, S)\) in the end.
  • The transition formula is \(f(i, s) = f(i - 1, s - a_i) + f(i - 1, s + a_i)\).
  • And the basecase is \(f(0, 0) = 1\)
  • Note we can do this in a breadth first search fashion, and once we move to \(f(i, ?)\) we can discard saved results for \(f(i - 2, ?)\)
def target_sum(nums, S):
    if not nums: return 0
    level = defaultdict(int)
    level[0] = 1
    for num in nums:
        next_level = defaultdict(int)
        for val in level:
            next_level[val + num] += level[val]
            next_level[val - num] += level[val]
        level = next_level
    return level[S]

322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Thought process:

  • Let \(f(a)\) be the minimal number of coins needed to sum up to amount \(a\)
  • The transition formula is \(f(a) = min({f(a - c) for c in coin_values}) + 1\)
def coin_change(coins, amount):
    min_coin = min(coins)
    dp = [0] + [float('inf')] * amount
    for amt in range(amount + 1):
        if amt < min_coin: continue
        dp[amt] = min({dp[amt - c] for c in coins if amt >= c}) + 1
    return dp[amount] if dp[amount] != float('inf') else -1

518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Thought process:

def change(amount, coins):
    dp = [1] + [0] * amount
    for c in coins:
        for amt in range(c, amount + 1):
            dp[amt] += dp[amt - c]
    return dp[amount]

1235. Maximum Profit in Job Scheduling

INF = 2 ** 32
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted([(e,s,p) for s, e, p in zip(startTime, endTime, profit)])
        dp = [[0, 0]]  # end time and max_profit 
        for e, s, p in jobs:            
            prev = bisect.bisect_right(dp, [s, INF]) - 1
            if dp[prev][1] + p > dp[-1][1]:
                dp.append([e, dp[prev][1] + p])
        return dp[-1][1]

1751. Maximum Number of Events That Can Be Attended II

class Solution:
    def maxValue(self, events: List[List[int]], K: int) -> int:
        events.sort(key=lambda x: x[1])
        dp, ndp = [[0, 0]], [[0, 0]]
        for k in range(K):
            for s, e, v in events:
                i = bisect.bisect_left(dp, [s]) - 1
                if dp[i][1] + v > ndp[-1][1]:
                    ndp.append([e, dp[i][1] + v])
            dp, ndp = ndp, [[0, 0]]
        return dp[-1][-1]

Buy and Sell Stock

123. Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

# action buy sell idle
# states init bought 1 sold 1 bought 2 sold 2
# state transition
#
# |---          |-----                   |------             |-----                        |-----
# V idle        V    idle                V   idle            V    idle                     V     idle
# init -buy-> 1st buy ---------sell---->sold 1st------buy-> 2nd buy-----------sell-------->sold 2nd
#
# immediate sell will result gain 0, which is equal to idle. 
INT_MIN = -2 ** 32

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #         init, bought 1, sold 1, bought 2, sold 2
        states = [0,    INT_MIN,       0,  INT_MIN,      0]    # amt of money at each state. 
        for price in prices:
            i, b1, s1, b2, s2 = states
            b1 = max(b1, i - price)   # idle or init-buy->b1; buy cheap 
            s1 = max(s1, price + b1)  # idle or b1-sell->s1;  sell high
            b2 = max(b2, s1 -price)   # idle or s1-buy->b2;   buy cheap
            s2 = max(s2, price + b2)  # idle or b2-sell->s2;  sell high
            states = [i, b1, s1, b2, s2]
        return s2

188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Extend 123 solution to k bought and k sold states

INT_MIN = -2 ** 32

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = [[0, 0]] + [[INT_MIN, 0] for _ in range(k)]
        for price in prices:
            for i in range(1, k+1):
                dp[i][0] = max(dp[i][0], dp[i-1][1] - price)
                dp[i][1] = max(dp[i][1], price + dp[i][0])
        return dp[k][1]                

Math, Geometry

1259. Handshakes That Don’t Cross

Consider connect people 1 with people i in (2, 4, 6, …) which seperate the people into two groups of size (i - 2) and (n - i). Each group is a problem of a smaller size and should be multiplied and summed over i to answer the current problem.

MOD = 10**9 + 7

class Solution:
    def numberOfWays(self, numPeople: int) -> int:
        @cache
        def f(n):
            if n == 0: return 1
            total = 0
            for i in range(2, n + 1, 2):
                total += f(i - 2) * f(n - i)
                total %= MOD
            return total
        return f(numPeople)

1478. Allocate Mailboxes

  • Double DP!!!!
  • First 2D DP to solve the cost to put one mailbox to minimize total distance from [i: j] both inclusive
    • dp1[i,j] be the mincost to use one mailbox for house i to house j
    • dp1[i,j] = 0 if i == j
    • dp1[i,j] = xj- xi if j == i + 1
    • dp1[i,j] = dp1[i+1,j-1] + xj-xi otherwise
  • Then 2D DP to solve the minimal cost when k mailboxes are allowed
    • dp2[i,k] be the cost to use k mailbox for house 0 to house i
    • dp2[i,k] = min(dp2[j,k-1] + dp1[j+1,i]) for all j in range(0, i).
class Solution:
    def minDistance(self, houses: List[int], k: int) -> int:
        houses.sort()
        n = len(houses)
        
        @cache
        def get_cost(i, j):
            if i == j: return 0
            if j == i + 1: return houses[j] - houses[i]
            return get_cost(i+1, j-1) + houses[j] - houses[i]
        
        @cache
        def dp(i, k):
            if k > i: return 0
            if k == 1: return get_cost(0, i)
            return min(dp(p, k-1) + get_cost(p+1, i) for p in range(i))

        return dp(n-1, k)

(Sub) Sequence / string matching

115. Distinct Subsequences

prefix both s and t with space. f(i, j) = # matches using s[:j] against t[:i] (inclusive) f(i, j) = f(i, j-1) + I[s[j] == t[i]] * f(i-1, j-1)

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]
        dp[0] = [1] * (len(s) + 1)
        for i in range(1, len(t) + 1):
            for j in range(i, len(s) + 1):
                dp[i][j] = dp[i][j-1] + int(bool(t[i-1] == s[j-1])) * dp[i-1][j-1]
        return dp[-1][-1]

1682. Longest Palindromic Subsequence II

Expansion? f(i, j) length of the longest good palindromic subsequence, last matched character f(i, j) = f(i+1, j-1) + 2, s[i] if s[i] == s[j] and s[i] != last_used = max(f(i+1, j), f(i, j-1))

class Solution:
    def solution_top_down(self, s):
        n = len(s)
        @cache
        def f(i, j):
            if i >= j: return 0, ""
            if s[i] == s[j] and s[i] != f(i+1,j-1)[1]:  return 2 + f(i+1, j-1)[0], s[i]
            return max(f(i+1, j), f(i, j-1))
        return f(0, n -1)[0]
    
    
    def solution_bottom_up(self, s):
        n = len(s)
        dp = [[[0, ""]] * n for _ in range(n) ]
        for d in range(1, n):
            i, j = 0, d
            while 0 <= i < j < n:
                if s[i] == s[j] and s[i] != dp[i+1][j-1][1]:
                    dp[i][j] = [dp[i+1][j-1][0] + 2, s[i]]
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                i += 1; j += 1
        return dp[0][n-1][0]
    
    longestPalindromeSubseq = solution_bottom_up

1062. Longest Repeating Substring

Also see 1044.

class Solution:
    def solution_binary_search(self, S: str) -> int:
        D = [ord(c) - ord('a') for c in S]
        P = 26
        MOD = 10 ** 9 + 7

        def rolling_hash(L):
            # initial window            
            h = 0
            for c in D[:L]: h = (h * P + c) % MOD
            seen = defaultdict(list)
            seen[h].append(0)

            PP = P ** L % MOD
            # sliding window            
            for r, c in enumerate(D[L:], L):
                # update window
                #    shift left   emit the old left     adding the new right    
                h = (h * P    -   D[r - L] * PP     +   c) % MOD
                
                # collision detection
                if h in seen:
                    if any(S[start:start + L] == S[r-L+1:r+1] for start in seen[h]): return True
                seen[h].append(r-L+1)
            return False

        l, h = 1, len(S)
        while l < h:
            m = (l + h) >> 1
            if rolling_hash(m): # find l such that rolling_hash[l:] == False 
                l = m +1
            else:
                h = m
        return l - 1
    
    longestRepeatingSubstring = solution_binary_search