在上一节，我们掌握了求解动态规划问题的通用套路。但正如我们前面所说，通用思路存在一定的局限性——它提供给大家的毕竟是一种方向性的引导，至于能不能实实在在地用自己的双手解决掉一道具体的题目，更多还是看同学们自己的“造化”。

所谓“造化”，其实并不神秘，它就是指我们自己对题目和知识点的思考深度和吸收程度。“造化”是否到位，并不取决于天赋，而是取决于每一位同学自身对题目的量的积累和对解题技术的总结。

作为对通用解题套路的补充，本节笔者基于自己接触过的海量动态规划真题，结合个人对面试命题倾向的观察和思考，提取了两个学习性价比极高的重点解题模型。 模型可以帮助我们迅速地识别并解决掉一类问题，通过对重点模型进行学习，大家可以在实战中做到举一反N，大大提升我们做题的效率和专业程度。

0-1背包模型

⚡ 30 秒速记

• 每件物品只能选一次：要么放，要么不放
• 一维写法：dp[c] = max(dp[c], dp[c - w] + v)，dp[c] = 容量 c 内的最大价值
• 容量必须倒序遍历，正序会让同一件物品在一轮里被用多次，变成完全背包
• 时间 O(n × C)，空间 O(C)；容量特别大（比如 10^9）时这个解法就不行了
• 只有价值数组恢复不出选了哪些，要记清单得保留二维表或额外记录

0-1 背包就是每件物品要么放要么不放，dp[c] 记容量 c 以内能拿到的最大价值。 处理每件物品时，比较「不放」的 dp[c] 和「放」的 dp[c - w] + v，取大的。压成一维后最关键的一点是容量要从大往小遍历：从小往大的话，dp[c - w] 已经是这一轮放过当前物品的值了，同一件物品就会被放好几次。我一般会拿一个物品、容量是它重量几倍的用例验证一下顺序写没写对。

回答参考：“0-1 的关键是每件只能用一次，所以一维 dp 倒序更新；若正序，同一物品的新状态会被本轮再次读取，悄悄变成完全背包。”

💬 面试官追问

• 容量循环改成从小到大，会出什么问题？

  同一件物品会被重复放。比如重量 2、价值 3，容量 6：正序时 dp[2] = 3，dp[4] 读到这一轮的 dp[2] 得 6，dp[6] 再得 9，相当于放了三次。

• 那如果需求就是每件物品可以无限拿呢？

  那就是完全背包，正好用正序遍历，转移公式一个字都不用改，只是循环方向反过来。

• 物品数 100、容量 10^9，还能用这套吗？

  不能，dp 数组开不出来。要看价值的范围，价值总和不大就反过来定义 dp[v] = 拿到价值 v 的最小重量；都很大就只能考虑搜索加剪枝之类的办法。

• 除了最大价值，还要告诉用户选了哪几件，怎么办？

  一维数组恢复不了。保留二维表 dp[i][c]，从 dp[n][C] 往回看：dp[i][c] !== dp[i-1][c] 说明第 i 件被选了，容量减掉它的重量继续往前看。

0-1背包问题是一个基本问题，基于这个基本问题，可以衍生出千姿百态的变种问题，这种题目就非常适合拿来构造解题模型。