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

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

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

0-1背包模型

⚡ 30 秒速记

• dp[c] 表示容量不超过 c 时的最大价值。
• 每件物品只有选/不选两种；一维压缩后容量必须倒序，避免同一物品本轮重复使用。
• 转移：dp[c] = max(dp[c], dp[c-weight] + value)。
• 时间 O(nC)、空间 O(C)；容量巨大时要考虑值域 DP 或其他算法。

0-1 背包用 dp[c] 表示容量不超过 c 时能取得的最大价值，每件物品只能选择一次或不选。 一维状态的转移是 dp[c] = max(dp[c], dp[c-weight] + value)，它比较不放当前物品和放入当前物品两种结果。容量必须从大到小更新，因为正序会读到本轮刚写入的状态，让同一件物品被重复使用，问题就变成了完全背包。该做法时间复杂度为 O(nC)、空间复杂度为 O(C)；如果容量特别大，还要考虑值域 DP 或其他算法。

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

💬 面试官追问

• 代码评审里有人把容量循环改成从小到大，声称 Math.max 会自动避免重复选择；用一个重量能被容量容纳多次的物品，结果会发生什么？

  结果可能在同一轮多次计入该物品，因为较大容量会读取本轮刚更新的 dp[c-weight]。Math.max 只比较候选价值，并不限制物品使用次数；这段代码的语义已经悄悄接近完全背包，违反每件物品只能选一次的约束。

• 商品组合页有数百件候选商品，前端只需计算容量上限内的最大价值，不展示具体清单；你会怎样落地 0-1 背包状态？

  可用长度为容量加一的一维 dp 数组，外层逐件遍历商品，内层容量从上限倒序到当前重量。这样每次转移仍读取上一轮语义的状态，并省去完整二维表；若之后要恢复商品清单，仅保留价值数组就不够，需要追加来源记录。

• 产品经理把规则改成同一种商品可选任意件，但开发仍坚持倒序容量更新；页面会漏掉哪类最优组合？

  倒序更新会让本轮无法复用刚写入的状态，因此同一商品仍最多贡献一次，可能漏掉重复选择该商品形成的更高价值组合。规则变成可重复选取后应改为正序容量更新；代价是模型语义变为完全背包，不能与原 0-1 约束混用。

• 线上组合结果异常偏大，日志显示只有一件重量为 2、价值为 3 的商品，容量为 6 时却得到 9；你会先查哪一层循环？

  先查容量循环是否从 2 正序走到 6，因为该顺序会依次读到本轮生成的 dp[2] 和 dp[4]，把同一件商品累计三次。修复为从 6 倒序到 2，再用单物品用例回归；若商品本就允许重复，则异常来自需求模型选错。