# Dynamic Programming

## 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]
```