代码随想录算法训练营 Day 30
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. KamaCoder 46
0-1背包问题：给定一堆物品，其中每个物品都有自己对应的重量和价值，现在要将这些物品放入背包之中，并且背包只能装一定重量的物品，求能够装下的最大价值
前四步：
- 使用二维的dp数组（数组大小为 $(m+1) \times (n+1)$），第一维代表物品，第二维代表重量，dp[i][j]代表着只考虑物品1到物品i，放进容量为j的背包的最大价值
- 递推公式：1. 物品i的重量大于j，那么此时物品i肯定无法被放入背包之中，因此dp[i][j] = dp[i - 1][j]；2. 物品i的重量不大于j，那么此时又有两种选择：1）不放入物品i，此时dp[i][j] = dp[i - 1][j]；2）放入物品i，此时dp[i][j] = dp[i - 1][j - weight[i]] + value[i]，物品i一定会被放入，那么就需要看用之前的物品放入剩余重量背包的最大价值，再加上物品i的价值。最终多种情况取最大值就是dp[i][j]的值
- 初始化：背包重量为0，无论什么物品都无法放入，因此dp[i][0] = 0. 不放入物品，背包里的价值也始终为0，因此dp[0][j] = 0. 其中情况会根据计算得到，因此初始化依然为0（保证取最大值的正确性）
- 遍历顺序：因为当前状态只和之前状态有关，因此两个遍历都是从前向后
m, n = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(n + 1):
if weight[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
print(dp[-1][-1])
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m \times n$)
Q2. KamaCoder 46
Q1中每一行的状态都可以由上一行得到，那么可以考虑将dp数组压缩成一维数组
前四步：
- 使用一维dp数组，dp[i]代表背包重量为i时，背包内可放入物品的最大价值
- 递推公式：依然和Q1类似，考虑两种情况
- 初始化：将整个dp数组初始化为0，也是Q1数组中的第一行
- 遍历顺序：遍历物品然后再遍历背包（顺序不可变！！！）。并且第二层循环需要从后往前遍历，dp[i]可能会用到前面的值，而这个值应该是没有更新过的，因此必须从后往前遍历
m, n = map(int, input().split())
weight = list(map(int, input().split()))
value = list(map(int, input().split()))
dp = [0] * (n + 1)
for i in range(m):
for j in range(n, -1, -1):
if j >= weight[i]:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp[-1])
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($n$)
Q3. LeetCode 416
将问题转化为0-1背包问题，其中背包的大小应该为总和的一半，物品的重量和价值都为数值本身
前四步：
- 使用一维dp数组，dp[i]代表背包重量为i时，背包内可放入物品的最大价值
- 递推公式：与Q1，Q2类似
- 初始化：将整个dp数组初始化为0
- 遍历顺序：遍历物品然后再遍历背包，注意背包需要从后往前遍历
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2 == 1:
return False
half_s = s // 2
dp = [0] * (half_s + 1)
for i in range(len(nums)):
for j in range(half_s, -1, -1):
if nums[i] <= j:
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
if dp[half_s] == half_s:
return True
return False
复杂度分析
时间复杂度：O($n^2$) 空间复杂度：O($n$)