一、课上练习

编程练习

1. 01背包问题：L3491
2. 采灵芝：L3492

二、知识总结

✨ 核心思想

滚动数组是一种空间优化技巧，用于将动态规划中的二维 dp 数组压缩为一维数组。当 dp 的状态转移只依赖于上一行（或前一层）的数据时，就可以使用滚动数组来节省空间。

✨ 01背包的滚动数组优化

在标准的01背包中，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

由于 dp[i] 只依赖于 dp[i-1]，可以将二维数组压缩为一维数组 dp[j]。

关键点：内层循环必须从大到小遍历容量，这样在更新 dp[j] 时，dp[j-w[i]] 还保留着上一轮（即 dp[i-1]）的值，保证每个物品只被选择一次。

for (int i = 0; i < n; i++) {
    for (int j = W; j >= wt[i]; j--) {  // 从大到小遍历
        dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
    }
}

✨ 执行示例

以 01 背包为例（3 个物品，容量 W=5），对比二维和一维滚动数组的执行过程：

物品0: 重量=1, 价值=6
物品1: 重量=2, 价值=10
物品2: 重量=3, 价值=12

一维滚动数组（从大到小遍历）：

初始：dp = [0, 0, 0, 0, 0, 0]

处理物品0（w=1, v=6），j 从 5 到 1：

j=5: dp[5] = max(dp[5], dp[4]+6) = max(0, 6) = 6
j=4: dp[4] = max(dp[4], dp[3]+6) = max(0, 6) = 6
j=3: dp[3] = max(dp[3], dp[2]+6) = max(0, 6) = 6
j=2: dp[2] = max(dp[2], dp[1]+6) = max(0, 6) = 6
j=1: dp[1] = max(dp[1], dp[0]+6) = max(0, 6) = 6

dp = [0, 6, 6, 6, 6, 6]

处理物品1（w=2, v=10），j 从 5 到 2：

j=5: dp[5] = max(dp[5], dp[3]+10) = max(6, 16) = 16
j=4: dp[4] = max(dp[4], dp[2]+10) = max(6, 16) = 16
j=3: dp[3] = max(dp[3], dp[1]+10) = max(6, 16) = 16
j=2: dp[2] = max(dp[2], dp[0]+10) = max(6, 10) = 10

dp = [0, 6, 10, 16, 16, 16]

处理物品2（w=3, v=12），j 从 5 到 3：

j=5: dp[5] = max(dp[5], dp[2]+12) = max(16, 22) = 22
j=4: dp[4] = max(dp[4], dp[1]+12) = max(16, 18) = 18
j=3: dp[3] = max(dp[3], dp[0]+12) = max(16, 12) = 16

dp = [0, 6, 10, 16, 18, 22]

答案：dp[5] = 22

关键观察： 从大到小遍历时，更新 dp[5] 使用的 dp[2]=10（还是上一轮的值），保证了物品2只被选择一次。如果从小到大遍历，dp[3] 先被更新为 16（已含物品2），dp[6]=dp[3]+12=28 就错误地选了物品2两次。

✨ 完全背包的滚动数组优化

完全背包的一维优化与01背包的区别在于内层循环从小到大遍历容量，这样 dp[j-w[i]] 使用的是当前轮（即 dp[i]）已更新的值，允许同一物品被多次选择。

for (int i = 0; i < n; i++) {
    for (int j = wt[i]; j <= W; j++) {  // 从小到大遍历
        dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);
    }
}

✨ 解题步骤详解

将二维 DP 优化为滚动数组的步骤：

1. 确认依赖关系：检查 dp[i][j] 只依赖于 dp[i-1][...]（上一行）
2. 去掉第一维：将 dp[i][j] 改为 dp[j]
3. 确定遍历顺序：
   • 如果依赖的是 dp[i-1][j']（上一行，j' <= j）：从大到小遍历（01背包）
   • 如果依赖的是 dp[i][j']（当前行，j' < j）：从小到大遍历（完全背包）
4. 调整循环范围：内层循环从 w[i] 开始（或到 w[i] 结束）

✨ 滚动数组的注意事项

使用滚动数组时需要特别注意以下几点：

• 遍历顺序至关重要：01背包从大到小，完全背包从小到大，顺序搞反会导致结果错误
• 初始化：一维 dp 数组通常初始化为 0（求最大值）或 INF（求最小值）
• 无法回溯路径：滚动数组丢弃了历史状态，如果需要输出具体选择方案，需要额外记录

三、课后练习

编程练习

1. 开心的金明：L3493