代码随想录算法训练营 Day 32
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. KamaCoder 52
完全背包问题：将物品放入背包中，每种物品数量无限个，求背包中能放下物品的最大价值
解法1
前四步：
- 使用二维的dp数组（数组大小为 $(m+1) \times (n+1)$），第一维代表物品，第二维代表重量，dp[i][j]代表着只考虑物品1到物品i，放进容量为j的背包的最大价值
- 递推公式：与0-1背包不同，因为物品数量是无限个，所以需要从本行中递推答案，而不是上一行。第一步操作是每一行的初始化，将上一行的结果复制，即 $dp[i] = dp[i - 1]$。如果背包容量大于物品重量，依然是两种情况：1. 物品不放入背包，此时数组不更新；2. 物品放入背包, $dp[i][j] = dp[i][j - weight]+value$，两者取最大值就是当前的dp值
- 初始化：背包重量为0，无论什么物品都无法放入，因此dp[i][0] = 0. 不放入物品，背包里的价值也始终为0，因此dp[0][j] = 0. 其中情况会根据计算得到，因此初始化依然为0（保证取最大值的正确性）
- 遍历顺序：从前向后遍历
m, n = map(int, input().split())
weight = []
value = []
for _ in range(m):
w, v = map(int, input().split())
weight.append(w)
value.append(v)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
dp[i] = dp[i - 1]
for j in range(1, n + 1):
if weight[i - 1] <= j:
dp[i][j] = max(dp[i][j], dp[i][j - weight[i - 1]] + value[i - 1])
print(dp[-1][-1])
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($m \times n$)
解法2
每一行的状态初始化都是复制上一行，那么可以考虑将dp数组压缩成一维数组
前四步：
- 使用一维dp数组，dp[i]代表背包重量为i时，背包内可放入物品的最大价值
- 递推公式：依然和Q1类似，考虑两种情况
- 初始化：将整个dp数组初始化为0，也是Q1数组中的第一行
- 遍历顺序：因为可以取多次相同物品，所以两层循环都是从前向后遍历
m, n = map(int, input().split())
weight = []
value = []
for _ in range(m):
w, v = map(int, input().split())
weight.append(w)
value.append(v)
dp = [0] * (n + 1)
for i in range(m + 1):
for j in range(weight[i - 1], n + 1):
dp[j] = max(dp[j], dp[j - weight[i - 1]] + value[i - 1])
print(dp[-1])
复杂度分析
时间复杂度：O($m \times n$) 空间复杂度：O($n$)
Q2. LeetCode 518
与0-1背包问题中的目标和类似，要找的是可能的组合数量，而非最大价值。区别在于本题中同一价值的硬币可以使用多次，因此需要转化为一个完全背包，背包容量为amount，物品价值和重量都是coin
前四步：
- 使用一维dp数组，dp[i]代表总和为i的组合有多少种
- 递推公式：1. 硬币数值比总和大，dp[i]无法更新；2. 否则，剩余的价值还需要考虑有多少种填充方法。因此 $dp[i] = dp[i] + dp[i - coin]$
- 初始化：将整个dp数组初始化为0，$dp[0] = 1$因为不找零只有一种方法
- 遍历顺序：从前向后遍历两层循环
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for i in range(len(coins)):
for j in range(amount + 1):
if j >= coins[i]:
dp[j] += dp[j - coins[i]]
return dp[-1]
复杂度分析
时间复杂度：O($amount \times n$) 空间复杂度：O($amount$)
Q3. LeetCode 377
前四步：
- 使用一维dp数组，dp[i]代表总和为i的排列有多少种
- 递推公式：1. 硬币数值比总和大，dp[i]无法更新；2. 否则，剩余的价值还需要考虑有多少种填充方法。因此 $dp[i] = dp[i] + dp[i - coin]$
- 初始化：将整个dp数组初始化为0，$dp[0] = 1$因为不找零只有一种方法
- 遍历顺序：需要先遍历总和（背包），然后遍历硬币（物品）
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for j in range(target + 1):
for i in range(len(nums)):
if nums[i] <= j:
dp[j] += dp[j - nums[i]]
return dp[-1]
复杂度分析
时间复杂度：O($target \times n$) 空间复杂度：O($target$)
Q4. KamaCoder 57
前四步：
- 使用一维dp数组，dp[i]代表可以爬到第i阶的方法数量
- 递推公式：需要计算排列数量，因此与Q3类似，$dp[i] += dp[i - j]$，其中j代表着这一步跨过的台阶数量
- 初始化：将整个dp数组初始化为0，$dp[0]=1$因为不跨出任何一步，就只能在起点
- 遍历顺序：需要寻找排列数量，因此先遍历总台阶，再遍历每一步的台阶数
n, m = map(int, input().split())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(n + 1):
for j in range(1, m + 1):
if i >= j:
dp[i] += dp[i - j]
print(dp[-1])
复杂度分析
时间复杂度：O($n \times m$) 空间复杂度：O($n$)