组合问题DP算法模版

* Recurrence:
SS(list,target) = SS(list[1:],target-list[0]) | SS(list[1:],target)
* Base case：
SS(list,0) = True

def subset_sum_dp(lst, target) -> bool:
    assert len(lst) != 0
    rec = [0] * (target+1)
    rec[0] = 1
    for v in lst:
        for t in reversed(range(v,target+1)):
            rec[t] |= rec[t-v]
        if rec[-1] != 0:
            return True
    return False

* Recurrence:
SS(list,target) = SS(list[1:],target-list[0]) + SS(list[1:],target)
* Base case：
SS(list,0) = 1

def subset_sum_num_dp(lst, target) -> int:
    rec = [0] * (target+1)
    rec[0] = 1
    for v in lst:
        for t in reversed(range(v,target+1)):
            rec[t] += rec[t-v]
    return rec[-1]

* Recurrence:
MC(coins,amount) = MC(coins,amount-coins[0]) | MC(coins[1:],amount)
* Base case:
MC(coins,0) = True

def make_change_dp(coins, amount) -> bool:
    assert len(coints) != 0
    rec = [0] * (amount+1)
    rec[0] = 1
    for c in coins:
        for i in range(c, amount+1):
            rec[i] |= rec[i-c]
        if rec[-1] != 0:
            return True
    return False

* Recurrence:
MC(coins,amount) = MC(coins,amount-coins[0]) + MC(coins[1:],amount)
* Base case:
MC(coins,0) = 1

def make_change_num_dp(coins, amount) -> int:
    rec = [0] * (amount+1)
    rec[0] = 1
    for c in coins:
        for i in range(c, amount+1):
            rec[i] += rec[i-c]
    return rec[-1]

def knapsack_dp(W, P, T) -> int:
    assert len(W) == len(P)
    rec = [0] * (T+1)
    for i,w in enumerate(W):
        for t in reversed(range(w,T+1)):
            rec[t] = max(rec[t], rec[t-w]+P[i])
    return rec[-1]

举出一个反例：

有三件物品，重量分别为10,6,1，价值分别为24,20,1，包大小为12。
使用Greedy，结果为：24+1+1=26
最优解为：20+20=40

def knapsack_complete_dp(W, P, T) -> int:
    assert len(W) == len(P)
    rec = [0] * (T+1)
    for i,w in enumerate(W):
        for t in range(w, T+1):
            rec[t] = max(rec[t], rec[t-w]+P[i])
    return rec[-1]