0Pricing
Coding Interview Prep · 课时

空间优化的背包

将二维状态压缩为单行

空间优化的背包 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

为什么要优化空间

完整表格需要 n 乘 cap 的内存，在输入规模较大时可能急剧膨胀。空间优化可以将其缩减为一个反复使用的行。

只需要最后一行

请注意，每个单元格只读取上一行，从不读取更早的内容。因此，您实际上不需要同时保存整个网格。

压缩为一个数组

保留一个长度为 cap+1 的 dp 数组。处理每件物品时，直接在原数组上覆盖，使它表示新的一行。

dp = [0] * (cap + 1)

重复使用陷阱

如果从左到右遍历容量，dp[w - wt[i]] 可能已经在处理同一件物品时被更新过。这样就会允许您将第 i 件物品拿取两次。

反向遍历容量

解决方法是从大到小遍历容量。向后遍历可以保证 dp[w - wt[i]] 仍然保存上一件物品处理后的值。

for w in range(cap, wt[i] - 1, -1):
    dp[w] = max(dp[w], val[i] + dp[w - wt[i]])

为什么反向遍历有效

计算 dp[w] 时，较小的下标 w - wt[i] 在这一轮中仍然未被修改，因此它仍然表示预期的上一行数据。

提前停止在物品重量处

wt[i]处停止。跳过这些容量只会节省一些无关紧要的循环次数。

完整循环

完整解法是在一个数组上进行两层嵌套循环。外层遍历物品，内层让容量反向遍历，答案自然就会得到。

for i in range(n):
    for w in range(cap, wt[i] - 1, -1):
        dp[w] = max(dp[w], val[i] + dp[w - wt[i]])

读取最终单元格

处理完所有物品后，dp[cap] 保存最大价值。它与二维表得到的数字相同，但所需内存少得多。

时间相同，内存更少

算法并没有加速；它仍然需要 n 乘 cap 级别的计算。您只是将内存需求从二次降到了线性。

何时值得使用

当 cap 很大、二维网格会超出内存限制时，这个技巧可以解决问题。它是竞赛中值得记住的常用技巧。

快速检查

测试一维背包的关键规则。

回顾

您已经将二维表压缩成一个数组，并通过让容量反向遍历来保证正确性，用线性内存替代了二次内存。🚀

常见问题解答

「空间优化的背包」课时是免费的吗？

是的 — 「空间优化的背包」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「空间优化的背包」这节课中我会学到什么？

将二维状态压缩为单行 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。

「空间优化的背包」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 0/1 背包：取或不取
  2. 空间优化的背包
  3. 完全背包与换零钱 DP
  4. 子集和与划分
← 返回 Coding Interview Prep