0-1背包
- 每个物品只能使用一次
- 非降维版本1 (dp[i][j]: 0,...,i)
- 目标：dp[n-1][bagWeight]
- 初始化根据物品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)
- 目标：dp[n][bagWeight]
- 初始化根据递推逻辑来处理，这样只需遍历全部物品即可。方便初始化
// 初始化 dp
vector<vector<int>> dp(weight.size()+1, vector<int>(bagweight + 1, 0));
for(int i = 1; i < weight.size()+1; i++) { // 遍历物品,从i=1开始, 对应物品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]: 对应非降维版本2)
- 内层遍历背包需要逆序
// 初始化
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]: 对应非降维版本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开始, 对应物品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]);
}
}
- 降维版本 （对应非降维版本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]);
}
}
- 降维版本等价写法 （对应非降维版本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个数
# 注意初始化方式，后面需要取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个数
# 注意初始化方式，后面需要取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 中的所有值 互不相同
-
完全背包 + 组合(先物品后背包)
- 物品：硬币（每个可以无限使用）
- 背包：金额数
- 如果要求返回全部方案组合，需要用dfs/回溯 搜索。这里只需要返回方案组合的数目，所以考虑用DP.
- dp[j]: 凑成金额j的组合总数。
- 复杂度. 时间：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]
- 这里涉及到组合问题，需要去重。先物品后背包可以去重。如果先背包后物品会有重复计算 (1+2 = 2+1 = 3).
377. 组合总和 Ⅳ
- 思路
- example
- 类似零钱兑换 II,但是这里是要求排列总和（不是组合总和）
-
如果要求返回全部方案，需要用回溯（排列问题）法。
- dp[j]: 凑成j的排列总数
- 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]
- 遍历顺序：先背包再物品
- 复杂度. 时间：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]
- 应该用爬楼梯框架来理解更容易。不要用背包问题框架去解释！！！
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?
例如，假设数组 nums 中含有正整数 a 和负整数 −b（其中 a>0,b>0,−b<0），则有 a×b+(−b)×a=0，对于任意一个元素之和等于 target 的排列，在该排列的后面添加 b 个 a 和 a 个 −b 之后，得到的新排列的元素之和仍然等于 target，而且还可以在新排列的后面继续 b 个 a 和 a 个 −b。因此只要存在元素之和等于 target 的排列，就能构造出无限长度的排列。
如果允许负数出现，则必须限制排列的最大长度，避免出现无限长度的排列，才能计算排列数。
