1. 动态规划
- 三要素：定义状态，分解子问题（找到迭代公式），设置边界条件
- 三种解题思路：
- Brutal Force Search
- Top Down（回溯+剪枝）
- Bottom Up（memorization）
2. 解题模板
2.1 题目定义
- (v[i]) 第i件物品的价值
- (w[i])第i件物品的重量
- (C)背包的总容量
- 是否可重复
2.2 状态转移方程
设(dp[i, j])，有i个物品，背包剩余容量为j。则动态转移方程：
2.1 【存在性】是否能够恰好装满容量为C的背包
[f(i, j) = egin{cases}
f(i-1, j)|f(i-1, j-w[i])& ext{without repetition}\
f(i-1, j)|f(i-1, j-w[i])|cdots f(i-1, j-k imes w[i])& ext{with repetition}
end{cases}]
2.2 【计数】容量为C的背包最多/少可以装多少东西
[f(i, j) = egin{cases}
max{f(i-1, j-w[i])+1, f(i-1, j)}& ext{without repetition}\
max{f(i-1, j-k imes w[i]) + k mid k in [0, frac{C}{v[i]}]}& ext{with repetition}
end{cases}]
2.3 【计数】装满容量为C的背包一共有多少方案
[f(i, j) = egin{cases}
f(i-1, j-w[i]) + f(i-1, j)& ext{without repetition}\
sum_0^{C//v[i]} f(i-1, j-k imes w[i]) mid k in [0, frac{C}{v[i]}]}& ext{with repetition}
end{cases}]
3. 例题
3.1 LeetCode 474.一和零
class Solution:
def findMaxForm_TopDown(self, strs: list, m: int, n: int) -> int:
# knapsack problem without repitition
# recursion equation (take it or leave it):
# f(i, m, n) = max{f(i-1, m-numZeros[i], n-numOnes[i]) + 1, f(i-1, m, n)}
# f(i, m, n) implies the maximum amount of strings that m 0s and n 1s can spell out.
# TOP-DOWN
def getMaxAmount(strs, m, n):
if strs and m >= 0 and n >= 0 and not (m == 0 and n == 0):
num_TakeIt = getMaxAmount(strs[1:], m - strs[0].count('0'), n - strs[0].count('1')) + 1
num_LeaveIt = getMaxAmount(strs[1:], m, n)
return max(num_TakeIt, num_LeaveIt)
elif not strs or m <= 0 or n <= 0:
if m >= 0 and n >= 0: return 0
else: return -1 # if m < 0 or n < 0 or not strs:
return getMaxAmount(strs, m, n)
def findMaxForm_BottomUp(self, strs: list, m: int, n: int) -> int:
import numpy as np
# BOTTOM-UP
dp = np.zeros((len(strs)+1, m+1, n+1), dtype=np.int32)
# Initialization
for i in range(m+1):
for j in range(n+1):
dp[0, i, j] = 0
for i in range(1, len(strs)+1):
dp[i, 0, 0] = 1
for i in range(1, len(strs)+1):
for j in range(m+1):
for k in range(n+1):
if j - strs[i - 1].count('0') >= 0 and k - strs[i - 1].count('1') >= 0:
dp[i, j, k] = max(dp[i-1, j-strs[i-1].count('0'), k-strs[i-1].count('1')] + 1, dp[i-1, j, k])
else:
dp[i, j, k] = dp[i-1, j, k]
return int(dp[len(strs), m, n])
两种方案都超时了，但是重要的是思路给掌握了。代码以后还要继续优化，使之通过OJ。超时的数据：
["0","0","1","1","1","0","1","0","0","1","1","0","1","0","1","0","1","0","0","1","0","1","0","0","1","1","1","0","1","1","0","0","1","1","1","0","1","0","0","0","1","0","1","0","0","1","0","0","1","1","1","1","1","0","0","1","0","1","0","1","1","0","0","0","1","1","1","1","1","1","0","1","1","1","0","0","1","1","0","0","1","1","0","1","0","0","1"]
93
91
["0","11","1000","01","0","101","1","1","1","0","0","0","0","1","0","0110101","0","11","01","00","01111","0011","1","1000","0","11101","1","0","10","0111"]
9
80
3.2 LeetCode518.零钱兑换2
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
import numpy as np
dp = np.zeros([len(coins) + 1, amount + 1])
for i in range(0, len(coins) + 1): dp[i, 0] = 1
for j in range(1, amount + 1): dp[0, j] = 0
for i in range(1, len(coins) + 1):
for j in range(1, amount + 1):
dp[i, j] = dp[i - 1, j]
if j-coins[i-1] >= 0: dp[i][j] += dp[i][j-coins[i-1]];
return int(dp[-1, -1])