Dynamic-Programming

general strategy

1. Start with the recursive backtracking solution
2. Optimize by using a memoization table (top-down[3] dynamic programming)
3. Remove the need for recursion (bottom-up dynamic programming)
4. Apply final tricks to reduce the time / memory complexity

When to use

• Input cannot sort
• Find minimum/maximum result
• Check the feasibility 找可行性
• Count all possible solutions 列出所有解 (Find count)

Principles

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势
http://klausguan.com/2017/07/09/dynamic-programing/
ACM动态规划总结

Memorization + Search

e.g.
http://univasity.iteye.com/blog/1170216

Minmax

https://segmentfault.com/a/1190000013527949

Minimax is to deep search for the best value, assuming the opponent will always play the move with the worst value (worst for us, so best for them).

Classical Problems

Regex Matching

# https://leetcode.com/problems/regular-expression-matching/description/
def isMatch(self, s, p):
    if len(p) == 0:
        return len(s) == 0
    
    dp = [[False] * (len(p)+1) for _ in range(len(s)+1)]
    dp[0][0] = True

    for j in range(1, len(p)+1):
        if p[j-1] == '*' and j >=2:
            dp[0][j] = dp[0][j-2]
    
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if s[i-1] == p[j-1] or p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
                
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2] or dp[i][j-1] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2]=='.'))
    return dp[-1][-1]

# see also https://leetcode.com/problems/wildcard-matching/description/

LIS (Linear)

Edit Distance (2D Array)

Backpack

guess money

def getMoneyAmount(self, n):
    dp = [[0] * (n+1) for _ in range(n+1)]
    #top-down search + memorization
    def solve(low, high):
        if low >= high:
            return 0
        if dp[low][high] == 0 and low < high:
            dp[low][high] = min([k + max(solve(low, k-1), solve(k+1, high)) for k in range(low, high)])
        return dp[low][high]
    return solve(1, n)

    # dp
    for gap in range(1, n):
        for low in range(1, n-gap+1):
            high = low + gap
            dp[low][high] = min([k + max(dp[low][k-1], dp[k+1][high]) for k in range(low, high)])
    return dp[1][n]

best time to buy and sell stock

# buy 1 sell 1
# track current min and max 
# Time O(N) Space O(1)
def maxProfit(self, prices):
    if len(prices) <= 1:
        return 0
    max_profit = 0
    min_buy = None
    for i in range(len(prices)):
        # No profit first day since no stock to sell
        if min_buy is None:
            min_buy = prices[i]
        else:
            max_profit = max(max_profit, prices[i] - min_buy)
            min_buy = min(min_buy, prices[i])
    return max_profit

# buy sell unlimited
# Time O(N) Space O(1)
def maxProfit_unlimited(self, prices):
    if len(prices) <= 1:
        return 0
    profit = 0
    curr_buy = None
    for i in range(len(prices)):
        if curr_buy is None:
            curr_buy = prices[i]
        else:
            if curr_buy < prices[i]:
                # accumulate all profit day by day
                profit +=  prices[i] - curr_buy
                curr_buy = prices[i]
            else:
                curr_buy = prices[i]
    return profit
# <= k transactions
# Time O(N * k) Space O(k)
def maxProfit_k(k, prices):
    if len(prices) < 2 or k < 1:
        return 0 
    if k > len(prices)/2:
        return self.maxProfit_unlimited(prices)
    else:
        buy = [-float('Inf') for _ in range(k)]
        sell =[-float('Inf') for _ in range(k)]
        buy[0] = -prices[0]
        
        # reverse order when moving to next day (or create a copy of previous dp) to avoid overwrite
        for i in range(1, len(prices)):
            for kk in reversed(range(1, k)):
                sell[kk] = max(sell[kk], buy[kk] + prices[i])
                buy[kk] = max(buy[kk], sell[kk-1] - prices[i])
            sell[0] = max(sell[0], buy[0] + prices[i])
            # deal with corner case of buy[0]
            buy[0] = max(buy[0], -prices[i])
        return max([0] + sell)

# unlimited transactions with 1 day cool down
# Time O(N) Space O(N)
def maxProfit_unlimited_cool_down(self, prices):
    if len(prices) < 2:
        return 0
    hold = [None] * len(prices)
    empty = [None] * len(prices)
    hold[0] = - prices[0]
    empty[0] = 0
    for i in range(1, len(prices)):
        empty[i] = max(empty[i-1], hold[i-1] + prices[i])
        hold[i] = max(hold[i-1], empty[i-2] - prices[i] if i > 1 else -prices[i])
    return max(empty[-1], hold[-1])

word break

#DP
# Time: O(N^2) Space: O(N)
# https://leetcode.com/problems/word-break/description/
def wordBreak(self, s, wordDict):

    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s)+1):
        for j in range(i):
            if dp[j] == True and s[j:i] in wordDict:
                dp[i] = True
    return dp[-1]

# DFS + memorization
# Time complexity  O(N^3): 
# Size of recursion tree can go up to n^2 The creation of list takes n time.
# Space complexity O(N^3): 
# ​​ The depth of the recursion tree can go up to n and each activation record can contains a string list of size n.
def wordBreak2(self, s, wordDict):
    dic = defaultdict(list)
    
    def dfs(word):
        if word not in dic:            
            res = []
            for w in wordDict:
                if word[:len(w)] == w:
                    if len(word) == len(w):
                        res.append(w)
                    else:
                        dfs_res = dfs(word[len(w):])
                        for r in dfs_res:
                            if r:
                                res.append(w + ' ' + r)
            dic[word] = res
        return dic[word]
    
    res = dfs(s)
    return res