# Coding Questions - Dynamic Programming¶

General DP solution steps: 1. Think in a divide and conquer way 2. Each sub-step should have overlap between each other 3. Build an eqaution between current step’s optimum solution and prev’s solution

**solution have optimal substructure and overlapped subproblems**

- Wild Card Match
- *. Recursive Thinking
Base Case ? Case * Case which needs to build solution recursively

- *. Once you have Recursive Solution, you can either
Use memoization to improve time complexity Use DP to imporove time complexity

*. T(n) = T(n-1) + T(n-2) –> O(2**n)

We can reduce the time complexity to polynomial time O(mn)!

- Frog Jump
Same as above solution, you can build recursive solution first!

- House Robber
- Solution::
# Recursive class Solution(object):

- def rob(self, nums):
“”” :type nums: List[int] :rtype: int “”” self.money = 0

- def helper(idx, nums, curr, robbed):
- if idx == len(nums):
self.money = max(self.money, curr) return

- if not robbed:
helper(idx+1, nums, curr+nums[idx], True) helper(idx+1, nums, curr, False)

- else:
helper(idx+1, nums, curr, False)

helper(0, nums, 0, True) helper(0, nums, 0, False) return self.money

# DP def rob(self, nums):

“”” :type nums: List[int] :rtype: int “”” dp = [0]*(len(nums)+1) for i in range(1, len(nums)+1):

dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])

return dp[-1]

- Robber II:
max(rob_line(nums[:-1]), rob_line(nums[1:]))

Win or Lose

- Panlindromic string
When it comes to panlindromic string, think in a recursive way, you can check it layer by layer. And when build the DP solution, inner loop is from bottom to the top because of DP[i+1][j-1]

- Buy and Sell Stocks
*. If you get a diff array, that’s maxium sub-array problem which can be solved in DP or Divide and Conquer *. We can build a 2 Dimensional DP, trick is we don’t know how’s 1st transaction like thus we need to have additional for loop to check this:

# This is also a great example to reduce time complexity. class Solution(object): def maxProfit(self, prices): k = 2 # at most 2 transactions dp = [[0]*(len(prices)+1) for _ in range(k+1)] for i in range(1, k+1): for j in range(1, len(prices)+1): tmpProfit = 0 for pos in range(1, j): tmpProfit = max(tmpProfit, prices[j-1]-prices[pos-1]+dp[i-1][pos]) dp[i][j] = max(dp[i][j-1], tmpProfit) return dp[-1][-1]

Maximum subarray problem

Knapsack problem

Build Stairs

Fibonacci

## LeetCode 691. Stickers to Spell Word¶

- First thought should be how to solve it using navie method
- 2nd thought should be able to find some recusion pattern
- 3rd thought should be able to come up with DP optimization

solution:

```
#hello world
```

## Knapsack problem - 0/1 Knapsack¶

You are the owner of a local store and you have a budget of N to spend on purchasing goods, different suppliers have different bundle options with different prices. You can buy **only one bundle** from each supplier untill the budget is used off. What’s your max units you can get using N budget?

This is 0/1 knapsack because you either choose or not.

可以利用一维的**滚动**数组模拟二维数据

另外由于这里由i−1的前面的解j−c[i]推导出i后面的解j，也就是利用一维的数据的话，旧解为前面的解，新解为后面的． 那么就应该让j从大到小进行循环遍历，因为这样第一次接触的到为旧解i−1，新出来的新解j在此次遍历也不会再用到．

另一个小的常数时间优化

在利用dfs递归求解时，先将物品按照单位价格排好序，单位价格高的靠前，这样如果某个物品超载时，没必要再累积其后面物品的价格， 而是按照该物品的单位价格乘以剩余容量，这样算出的总价格虽然比实际装载的总价格略高些，如果这样略高于实际值的解还低于当前的最优解，则可对后面剪枝，避免多余的计算．

http://www.hawstein.com/posts/dp-knapsack.html http://blog.csdn.net/u010106759/article/details/77984537

Solution and Explaination:

```
class Solution(object):
def knapsack(self, n, bundles, costs):
# this is a 0/1 knapsack problem, we can only choose True/False once for each position.
# dp[i][j] means the max bundles when we have i choices with j costs.
dp = [[0]*(n+1) for _ in range(len(bundles)+1)]
for i in range(1, len(bundles)+1):
for j in range(1, n+1):
if j >= costs[i-1]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-costs[i-1]]+bundles[i-1])
print dp
return dp[-1][-1]
# although we can compress the space complexity but the time complexity keeps the same
# therefore we still have 2 loops.
def knapsack_1(self, n, bundles, costs):
# dp[j] means the max bundles when we have i choices with j costs.
dp = [0]*(n+1)
for i in range(1, len(bundles)+1):
# each time when we have dp, it keeps last states which is i-1
# Since we have dp[j-costs[i-1]] part, i-1 status will be lost if we update it first,
# we need to do it from the end to the front.
for j in range(n, -1, -1):
if j >= costs[i-1]:
dp[j] = max(dp[j], dp[j-costs[i-1]]+bundles[i-1])
return dp[-1]
def beautiful_print(data):
if type(data) is list and type(data[0]):
for value in data:
print value
print Solution().knapsack_1(38, [3, 5, 4], [10, 20, 16])
# Below solution is wrong because i didn't consider the ordering!
def knapsack_new(self, n, bundles, costs):
dp =[(0, 0) for i in range(len(bundles)+1)]
for i in range(1, len(bundles)+1):
if n-dp[i-1][1] >= costs[i-1]:
dp[i] = (dp[i-1][0]+bundles[i-1], dp[i-1][1]+costs[i-1]) if dp[i-1][0]+bundles[i-1] > dp[i-1][0] else dp[i-1]
else:
dp[i] = dp[i-1]
return dp[-1][0]
```

## Knapsack problem - Unbounded Knapsack¶

You are the owner of a local store and you have a budget of N to spend on purchasing goods.
Different suppliers have different bundle options with different prices. You can buy **as many as
bundles** from each supplier untill the budget is used off. What’s your max units you can get using
N budget?

- Notation:
- Budget : N = 50BundleUnits : B = [5, 15, 20]BundlePrice : P = [5, 10, 15]MaxUnit : t = (50/10)*15=75

Thoughts:

0/1背包只考虑放与不放进去两种情况，而完全背包要考虑 放0,放1, ···, 放j/w[i] 的情况.

The unbonded problem can be converted to 0/1 knapsack problem:

```
for i in range(1, len(bundles)+1):
for j in range(n, -1, -1):
tmp = 0
for k in range(1, j/costs[i-1]+1):
tmp = max(tmp, dp[i-1][j-k*costs[i-1]] + bundles[i-1]*k)
dp[i][j] = max(tmp, dp[i-1][j])
```

Above solution’s time complexity is O(N*len(B)*sum(k)) which is a little high.

A simple optimiazation is to add one more check: if costs[i] < costs[i+1] and bundles[i]>bundles[i+1], then we can skip i+1 case.

- Another optimiazation is to divide last item to 0/1 problem using 2 as the base, then the loop goes to O(log(k)) instead of k.
这是二进制的思想. 因为, 不管最优策略选几件第 i 种物品, 其件数写成二进制后, 总可以表示成若干个 2^k 件物品的和.

In fact, this problem can be coverted to O(N*len(B)), the only difference is:

```
dp[i][j] = max(dp[i-1][j], dp[i][j-costs[i-1]]+bundles[i-1])
```

Instead of dp[i-1], dp[i] will contain all the possible solutions at i-1 (i’m still confused about this form and haven’t found a good way to explain)

- Try to understand this, i think it makes sense:
- dp[i][j-1]+v[i]代表至少放了一个第i种物品, 当然它的前提是能放进去（j>=w[i]）, 所以dp[i][j]=max{dp[i-1][j],dp[i][j-w[i] ]+v[i]}已经涵盖了一个都不放与至少放一个第i种物品的情况了.

## LeetCode 121. Best Time to Buy and Sell Stock¶

- If you were only permitted to complete at most one transaction::
# you can get max profix using one transaction in O(n) class Solution(object):

- def maxProfit(self, prices):
buy = float(‘inf’) sell = 0 for i in range(len(prices)):

buy = min(buy, prices[i]) sell = max(sell, prices[i]-buy)return sell

## LeetCode 122. Best Time to Buy and Sell Stock II¶

You may complete as many transactions as you like:

```
class Solution(object):
def maxProfit(self, prices):
# the idea is to capture every profit.
# you can sell and buy immediately at the same day
profit = 0
for i in range(1, len(prices)):
if prices[i]>prices[i-1]:
profit += prices[i]-prices[i-1]
return profit
```

## LeetCode 123. Best Time to Buy and Sell Stock III and IV¶

This is a standard DP solution, i think the hardest part to come up with the DP helper array,

**DP[i][j] means the profit you have at j with i transactions**

The state function is simple and you need to use the temp variable to reduce complexity:

```
class Solution(object):
def maxProfit(self, prices):
if len(prices) < 2:
return 0
# the 3rd inner loop to check each position and find max profit is unnecessary
# we can try to use a tmp variable to reduce the time complexity
k = 2
if len(prices) < 2:
return 0
# k is big enougth to cover all ramps.
if k >= len(prices) / 2:
return sum(i - j for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
dp = [[0] * (len(prices) + 1) for _ in range(k + 1)] # this means the max profit with k transctions.
for i in range(1, k+1):
# initial
tmpMaxProfit = dp[i - 1][0] - prices[0] # use this varaible to get the profit at each transctions
for j in range(1, len(prices)+1):
# dp[i][j] 1> dp[i][j-1]
# 2> for m in range(j-1]:
# prices[j-1] + dp[i-1][m] - prices[m]
# Explaination: 1> we used up all transactions before last stock
2> we leave the last transaction to j-1, we need to find the max profit we can make within (1, j-1]
# Since we are already checking all positions and 2> can be transformed to prices[j-1] + {dp[i-1] - prices[m]} for m in range(1, j)
# Then we can reduce the for loop to one variable.
# Trick is, the prev buy choice could be any price before j-1, thus you have to check or find the max local
# and that would be your new value, then use tmpMaxProfit
# tmpMaxProfit = dp[i-1][j] - prices[j-1]: use one variable to reduce the loop
dp[i][j] = max(dp[i][j - 1], tmpMaxProfit + prices[j-1])
tmpMaxProfit = max(tmpMaxProfit, dp[i - 1][j] - prices[j-1]) # initial for next level
return dp[-1][-1]
```

## LeetCode 309. Best Time to Buy and Sell Stock with Cooldown¶

Don’t worry, you can try to use the Brute Force to solve it first:

```
class Solution(object):
def maxProfit(self, prices):
# Solution 1:
# enumerate all the possible solutions and check for the max value
# Each position has 3 ways to do: O(3**n)
# Solution 2:
# Record max PROFIT value for each state
# hold[i] = max(hold[i-1], res[i-1]-prices[i]) - hold previous or buy current
# sold[i] = hold[i-1] + prices[i] - sell current
# rest[i] = max(res[i-1], sold[i-1])
# return max(sold[i], rest[i])
sold = 0
rest = 0
hold = float('-inf')
for price in prices:
prev = sold
hold = max(hold, rest-price)
sold = hold + price
rest = max(rest, prev)
return max(rest, sold)
# Solution 3:
# Record max PROFIT value for each state
# sell[i] - PROFIT when sell at day i
# cooldown[i] - PROFIT when day i is cooldown
if not prices or len(prices)<2:
return 0
n = len(prices)
sell = [0]*n
cool = [0]*n
sell[1] = prices[1]-prices[0]
for i in range(2, n):
cool[i] = max(sell[i-1], cool[i-1])
sell[i] = prices[i] - prices[i-1] + max(sell[i-1], cool[i-2])
return max(sell[-1], cool[-1])
```

## LeetCode 714. Best Time to Buy and Sell Stock with Transaction Fee¶

Solution:

```
class Solution(object):
def maxProfit(self, prices, fee):
# Solution 1:
# enumerate all the possible solutions and check for the max value
# Each position has 2 ways to do: O(2**n)
# Solution 2:
# Similar to with cooldown problem, we can use 2 arrays to record the state.
# buy[i] - PROFIT when we buy at day i BUY or NOT
# sell[i] - PROFIT when we sell at day i SELL or NOT
buy = [0] * len(prices)
sell = [0] * len(prices)
buy[0] = - prices[0]
sell[0] = 0
for i in range(1, len(prices)):
buy[i] = max(sell[i-1]-prices[i], buy[i-1]) # you have to sell before buy
sell[i] = max(buy[i-1]+prices[i]-fee, sell[i-1])
return sell[-1]
```

## Leetcode 53. Maximum Subarray¶

- This is a very basic problem which can be used to help you understand the following concepts:
- # Divide and Conquer # DP solution # DP solution with minimum space complexity

DP Solution:

```
dp = [0]*(len(nums)+1)
for i in range(1, len(nums)+1):
dp[i] = max(dp[i-1], dp[i-1]+nums[i-1])
return dp[-1]
```

This is my initial thought, however, this equation doesn’t meet the requirement of continous subarray. Keeping the condition in mind then we can reformat the condition a little bit:

DP[i] means the maximum subarray thatends at position i

The code should look like this:

```
def maxSubArray(self, nums):
dp = [float('-inf')]*(len(nums)+1)
for i in range(1, len(nums)+1):
dp[i] = max(nums[i-1], dp[i-1]+nums[i-1])
return max(dp)
```

If you want to reduce the space complexity, you can replace the DP array with 2 variables. Optimized DP solution:

```
def maxSubArray(self, nums):
maxEnding = float('-inf')
globalMax = float('-inf')
for i in range(len(nums)):
maxEnding = max(nums[i], maxEnding+nums[i])
globalMax = max(globalMax, maxEnding)
return globalMax
```

https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts https://discuss.leetcode.com/topic/4175/share-my-solutions-both-greedy-and-divide-and-conquer