0-1背包
- 每個物品只能使用一次
- 非降維版本1 (dp[i][j]: 0,...,i)
- 目標(biāo)：dp[n-1][bagWeight]
- 初始化根據(jù)物品0來確定
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagweight; j++) {
dp[0][j] = value[0];
}
for(int i = 1; i < weight.size(); i++) { // 遍歷物品,從i=1開始
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量，可以順序
if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 需要update dp[i][j]
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
- 非降維版本2 (dp[i][j]: 前i個，0,...,i-1)
- 目標(biāo)：dp[n][bagWeight]
- 初始化根據(jù)遞推邏輯來處理，這樣只需遍歷全部物品即可。方便初始化
// 初始化 dp
vector<vector<int>> dp(weight.size()+1, vector<int>(bagweight + 1, 0));
for(int i = 1; i < weight.size()+1; i++) { // 遍歷物品,從i=1開始, 對應(yīng)物品i-1
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量，可以順序
if (j < weight[i-1]) dp[i][j] = dp[i - 1][j]; // 需要update dp[i][j]
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i-1]] + value[i-1]);
}
}
- 降維版本 (dp[j]: 對應(yīng)非降維版本2)
- 內(nèi)層遍歷背包需要逆序
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 1; i < weight.size()+1; i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i-1]; j--) { // 遍歷背包容量， 逆序
dp[j] = max(dp[j], dp[j - weight[i-1]] + value[i-1]);
}
}
- 降維版本等價寫法 (dp[j]: 對應(yīng)非降維版本1)
// 初始化
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量， 逆序
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 遍歷順序
- 非降維版本可以交換
- 降維版本：先物品后背包 （背包逆序）
完全背包
- 每個物品可以使用多次
- 非降維版本1 (dp[i][j]: 0,...,i)
略
- 非降維版本2 (dp[i][j]: 前i個，0,...,i-1)
- 遞推公式：對每個物品：（不選 vs 選了>=1次）
// 初始化 dp
vector<vector<int>> dp(weight.size()+1, vector<int>(bagweight + 1, 0));
for(int i = 1; i < weight.size()+1; i++) { // 遍歷物品,從i=1開始, 對應(yīng)物品i-1
for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量，可以順序
if (j < weight[i-1]) dp[i][j] = dp[i - 1][j]; // 需要update dp[i][j]
else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i-1]] + value[i-1]);
}
}
- 降維版本 （對應(yīng)非降維版本2）
vector<int> dp(bagWeight + 1, 0);
for(int i = 1; i < weight.size()+1; i++) { // 遍歷物品
for(int j = weight[i-1]; j <= bagWeight ; j++) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i-1]] + value[i-1]);
}
}
- 降維版本等價寫法 （對應(yīng)非降維版本1）
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍歷背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 交換遍歷順序也可以
// 先遍歷背包，再遍歷物品
for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
for(int i = 0; i < weight.size(); i++) { // 遍歷物品
if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
- 遍歷順序
- 降維版本可交換，物品和背包都是順序遍歷
322. Coin Change
- 思路
- example
- coins 中的所有值 互不相同
- 完全背包
- 先物品，再背包: 二維DP (都是順序遍歷)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 完全背包
# dp[i][j]: coins[0,...,i-1] (方便處理初始化?), "amount" = j
k = len(coins)
# 注意初始化方式，后面需要取min,同時要滿足累加邏輯。
dp = [[amount+1 for _ in range(amount+1)] for _ in range(k+1)]
dp[0][0] = 0 # 實際上dp[i][0] = 0 for any i
for i in range(1, k+1): # 物品
# coins[i-1]
for j in range(amount+1): # 背包
if coins[i-1] > j: # 不能使用coins[i-1]
dp[i][j] = dp[i-1][j]
else: # 可以使用coins[i-1] （可能多個）
dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1)
# 可用而不使用 可用且使用若干個
return dp[k][amount] if dp[k][amount] != amount+1 else -1
- 先物品，再背包：一維DP (都是順序遍歷)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 完全背包
# dp[j]: 湊成金額j所需要的最小coins個數(shù)
# 注意初始化方式，后面需要取min,同時要滿足累加邏輯。
dp = [amount+1 for _ in range(amount+1)]
dp[0] = 0
for coin in coins: # 物品
for j in range(amount+1): # 背包
if coin > j: # 不能使用coin
dp[j] = dp[j] # 可刪掉(但遍歷下界是coin)，保留在這里方便對比邏輯
else: # 可以使用coin （可能多個）
dp[j] = min(dp[j], dp[j-coin]+1)
return dp[amount] if dp[amount] != amount+1 else -1
- 先物品，再背包: 二維DP (都是順序遍歷). 非前i個版本，初始化比較麻煩。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = len(coins)
dp = [[amount+1 for _ in range(amount+1)] for _ in range(n)]
dp[0][0] = 0
for j in range(amount+1):
if j >= coins[0]:
dp[0][j] = min(dp[0][j], dp[0][j-coins[0]] + 1)
for i in range(1, n):
coin = coins[i]
for j in range(amount+1):
if j < coin:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-coin]+1)
return dp[n-1][amount] if dp[n-1][amount] != amount+1 else -1
- 先背包，再物品：二維DP (都是順序遍歷)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 完全背包
# dp[i][j]: coins[0,...,i-1] (方便處理初始化?), "amount" = j
k = len(coins)
# 注意初始化方式，后面需要取min,同時要滿足累加邏輯。
dp = [[amount+1 for _ in range(amount+1)] for _ in range(k+1)]
dp[0][0] = 0 # 實際上dp[i][0] = 0 for any i
for j in range(amount+1): # 背包
for i in range(1, k+1): # 物品
# coins[i-1]
if coins[i-1] > j: # 不能使用coins[i-1]
dp[i][j] = dp[i-1][j]
else: # 可以使用coins[i-1] （可能多個）
dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i-1]]+1)
# 不使用 使用(可能多個)
return dp[k][amount] if dp[k][amount] != amount+1 else -1
- 先背包，再物品：一維DP (都是順序遍歷)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 完全背包
# dp[j]: 湊成金額j所需要的最小coins個數(shù)
# 注意初始化方式，后面需要取min,同時要滿足累加邏輯。
dp = [amount+1 for _ in range(amount+1)] # !!!
dp[0] = 0 # !!!
for j in range(amount+1): # 背包
for coin in coins: # 物品
if coin > j: # 不能使用coin
dp[j] = dp[j] # 可刪掉，保留在這里方便對比邏輯
else: # 可以使用coin （可能多個）
dp[j] = min(dp[j], dp[j-coin]+1)
return dp[amount] if dp[amount] != amount+1 else -1
518. 零錢兌換 II
- 思路
- example
- coins 中的所有值 互不相同
-
完全背包 + 組合(先物品后背包)
- 物品：硬幣（每個可以無限使用）
- 背包：金額數(shù)
- 如果要求返回全部方案組合，需要用dfs/回溯 搜索。這里只需要返回方案組合的數(shù)目，所以考慮用DP.
- dp[j]: 湊成金額j的組合總數(shù)。
- 復(fù)雜度. 時間：O(?), 空間: O(?)
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0 for _ in range(amount+1)]
dp[0] = 1 # !!!
for coin in coins:
for j in range(coin, amount+1):
dp[j] += dp[j-coin]
return dp[amount]
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
n = len(coins)
dp = [[0 for _ in range(amount+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
coin = coins[i-1]
for j in range(amount+1):
if j < coin:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-coin]
return dp[n][amount]
- 這里涉及到組合問題，需要去重。先物品后背包可以去重。如果先背包后物品會有重復(fù)計算 (1+2 = 2+1 = 3).
377. 組合總和 Ⅳ
- 思路
- example
- 類似零錢兌換 II,但是這里是要求排列總和（不是組合總和）
-
如果要求返回全部方案，需要用回溯（排列問題）法。
- dp[j]: 湊成j的排列總數(shù)
- e.g., 3 = [(0) + 3] + [(1) + 2] + [(2) + 1]
- dp[3] = dp[2] + dp[1] + dp[0]
- e.g., 3 = [(0) + 3] + [(1) + 2] + [(2) + 1]
- 遍歷順序：先背包再物品
- 復(fù)雜度. 時間：O(?), 空間: O(?)
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0 for _ in range(target+1)]
dp[0] = 1 # !!!
for j in range(target+1):
for num in nums:
if j >= num:
dp[j] += dp[j-num]
return dp[target]
- 應(yīng)該用爬樓梯框架來理解更容易。不要用背包問題框架去解釋?。?！
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0 for _ in range(target+1)]
dp[0] = 1
for j in range(1, target+1):
for num in nums:
if j >= num:
dp[j] += dp[j-num]
return dp[target]
- 2D: 比較麻煩
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
n = len(nums)
dp = [[0 for _ in range(target+1)] for _ in range(n+1)]
dp[0][0] = 1 # !!!
for j in range(target+1):
for i in range(1, n+1):
if j < nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
for k in range(1, n+1):
if j >= nums[k-1]:
dp[i][j] += dp[i][j-nums[k-1]]
return dp[n][target]
- Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
例如，假設(shè)數(shù)組 nums 中含有正整數(shù) a 和負(fù)整數(shù) ?b（其中 a>0,b>0,?b<0），則有 a×b+(?b)×a=0，對于任意一個元素之和等于 target 的排列，在該排列的后面添加 b 個 a 和 a 個 ?b 之后，得到的新排列的元素之和仍然等于 target，而且還可以在新排列的后面繼續(xù) b 個 a 和 a 個 ?b。因此只要存在元素之和等于 target 的排列，就能構(gòu)造出無限長度的排列。
如果允許負(fù)數(shù)出現(xiàn)，則必須限制排列的最大長度，避免出現(xiàn)無限長度的排列，才能計算排列數(shù)。
