我的 LeetCode 日记：Day 37 - 解锁动态规划：完全背包问题

在掌握了 0/1 背包之后，今天我将能力升级，开始学习动态规划中的另一大经典模型——完全背包问题。

它与 0/1 背包的核心区别只有一个：0/1 背包中的每个物品只有一个，只能选一次；而完全背包中的每个物品有无限个，可以重复选择。这个看似微小的改动，却对状态转移方程和代码实现，尤其是一维空间优化，产生了深刻的影响。

一、理论奠基：完全背包的核心差异

学习完全背包，关键是和 0/1 背包进行对比。

• 二维 DP: 在 0/1 背包中，状态转移方程是 dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i-1]])。我们总是从 dp[i-1] 这个“上一行”的状态转移而来。但在完全背包中，因为物品 i 可以重复选取，所以当我们决定放入一个物品 i 时，我们是基于“已经放入过物品 i”的状态来决策的。因此，状态转移方程变成了 dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i][j - weights[i-1]])。注意，这里是 dp[i] 而不是 dp[i-1]！

• 一维 DP (空间优化): 这个状态转移的差异，在一维 dp 数组中体现得淋漓尽致。0/1 背包为了使用 i-1 轮的状态，内层循环必须倒序遍历。而完全背包因为要使用第 i 轮的“最新”状态，内层循环必须正序遍历。这一个小小的遍历顺序，就是区分两种背包问题的关键所在。

• 理论指南:

  • 文章讲解: 代码随想录-完全背包理论基础
  • 视频讲解: B站视频-完全背包

我的实现 1：二维 DP

def solve_complete_knapsack_2d():n, v = map(int, input().split()) # 物品数量, 背包容量weights, values = [], []for _ in range(n):w, val = map(int, input().split())weights.append(w)values.append(val)dp = [[0] * (v + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, v + 1):if j < weights[i-1]:dp[i][j] = dp[i-1][j] # 不放物品ielse:# 关键区别：dp[i][...] 而不是 dp[i-1][...]dp[i][j] = max(dp[i-1][j], values[i-1] + dp[i][j - weights[i-1]])print(dp[n][v])

我的实现 2：一维 DP (空间优化)

def solve_complete_knapsack_1d():n, v = map(int, input().split())weights, values = [], []for _ in range(n):w, val = map(int, input().split())weights.append(w)values.append(val)dp = [0] * (v + 1)for i in range(n): # 遍历物品# 关键区别：正序遍历背包容量for j in range(weights[i], v + 1):dp[j] = max(dp[j], values[i] + dp[j - weights[i]])print(dp[v])

---

二、实战演练：完全背包的应用

1. LeetCode 518. 零钱兑换 II

题目描述: 给定不同面额的硬币和一个总金额。写一个函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

• 学习感悟: 这是典型的完全背包组合问题。
  • 背包容量: amount
  • 物品: coins 数组中的每种硬币
  • DP 定义: dp[j] 表示凑成金额 j 的组合数。
  • 状态转移: dp[j] += dp[j - coin]。凑成 j 的方法数，等于之前的方法数，加上“凑成 j-coin 的方法数”（因为这些方法都可以通过加上一个 coin 来凑成 j）。
  • 遍历顺序: 因为求的是组合数（{1, 2} 和 {2, 1} 算一种），所以必须先遍历物品（coins），再遍历背包（amount）。这样可以保证硬币是按固定顺序添加的，避免了重复计数。
• 资源包:
  • 题目/文章: https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
  • 视频讲解: https://www.bilibili.com/video/BV1KM411k75j

我的实现：一维 DP (组合问题)

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1 # 凑成金额0有一种方法：什么都不选# 先遍历物品，再遍历背包，求的是组合数for coin in coins:for j in range(coin, amount + 1):dp[j] += dp[j - coin]return dp[amount]

2. LeetCode 377. 组合总和 Ⅳ

题目描述: 给你一个由 不同 整数组成的数组 nums，和一个目标整数 target。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。

• 学习感悟: 这道题和上一题非常相似，但有一个本质区别：它求的是排列数（{1, 2} 和 {2, 1} 算两种）。这个小小的区别，只需要交换内外层循环的顺序即可解决。
  

  • 遍历顺序: 先遍历背包（target），再遍历物品（nums）。这样做的效果是，在计算 dp[j] 时，会依次尝试放入 nums 中的每一个数，这就考虑了不同的放入顺序，从而得到了排列数。

• 资源包:

  • 题目/文章: https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
  • 视频讲解: https://www.bilibili.com/video/BV1V14y1n7B6

我的实现：一维 DP (排列问题)

class Solution:def combinationSum4(self, nums: List[int], target: int) -> int:dp = [0] * (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]

3. LeetCode 70. 爬楼梯 (完全背包版)

• 学习感悟: 用完全背包的视角重新审视“爬楼梯”问题，豁然开朗！
  • 背包模型: 背包容量是楼梯总数 n。物品是每次能爬的步数（如 1 步、2 步，甚至 m 步）。因为每种步数可以重复使用，所以是完全背包。因为爬楼梯的顺序是重要的（先1后2 vs. 先2后1），所以是排列问题。
  • DP 定义: dp[j] 表示爬到第 j 阶楼梯的方法总数。
• 资源包: 代码随想录-70.爬楼梯(完全背包版)

我的实现：排列型完全背包

def solve_climbing_stairs(n, m):"""n: 楼梯总数m: 一次最多能爬的步数"""dp = [0] * (n + 1)dp[0] = 1# 先遍历背包（楼梯），再遍历物品（步数）for j in range(1, n + 1):for i in range(1, m + 1):if j >= i:dp[j] += dp[j - i]print(dp[n])

总结

今天我彻底搞清楚了完全背包和 0/1 背包的核心区别——一维 dp 数组的内层循环是正序还是倒序。更重要的是，我学会了通过调整内外层循环的顺序，来解决组合问题和排列问题，这个技巧非常精妙。用新的视角重看旧问题，也让我对 DP 模型的理解更加深入。