# Dynamic Programming

## Leetcode DP study plan list II

- Day 1 Basics of Dynamic Programming
- Day 2 One Dimensional Dynamic Programming
- Day 3 One Dimensional Dynamic Programming
- Day 4 One Dimensional Dynamic Programming
- Day 5 One Dimensional Dynamic Programming
- Day 6 One Dimensional Dynamic Programming
- Day 7 Dynamic Programming on String
- Day 8 Dynamic Programming on String
- Day 9 Dynamic Programming on String
- Day 10 Dynamic Programming on String
- Day 11 Dynamic Programming on String
- Day 12 Dynamic Programming on String
- Day 13 Min/Max Path Sum
- Day 14 Classic Dynamic Programming Problems
- 343. Integer Break
- 238. Product of Array Except Self # not really

- Day 15 Memoization
- 139. Word Break
- 254. Factor Combinations
- 329. Longest Increasing Path in a Matrix # google follow up return path rather than length

- Day 16 Unique Paths
- Out of Boundary Paths
- Unique Binary Search Trees
- Day 19 Coin Change / Combination Sum
- Day 20 Coin Change / Combination Sum
- Day 21 Partition Equal Subset Sum

## Leetcode DP study plan list III

- Day 1 Classic Dynamic Programming Problems
- Day 2 One Dimensional Dynamic Programming
- Day 3 One Dimensional Dynamic Programming
- Day 4 One Dimensional Dynamic Programming
- Day 5 Dynamic Programming on String
- 115. Distinct Subsequences
- 435. Non-overlapping Intervals # greedy really

- Day 6 Dynamic Programming on String
- 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
```