普通人也能吃透的动态规划思想专题（下）|算法篇
在上一节，我们掌握了求解动态规划问题的通用套路。但正如我们前面所说，通用思路存在一定的局限性——它提供给大家的毕竟是一种方向性的引导，至于能不能实实在在地用自己的双手解决掉一道具体的题目，更多还是看同学们自己的“造化”。
所谓“造化”，其实并不神秘，它就是指我们自己对题目和知识点的思考深度和吸收程度。“造化”是否到位，并不取决于天赋，而是取决于每一位同学自身对题目的量的积累和对解题技术的总结。
作为对通用解题套路的补充，本节笔者基于自己接触过的海量动态规划真题，结合个人对面试命题倾向的观察和思考，提取了两个学习性价比极高的重点解题模型。 模型可以帮助我们迅速地识别并解决掉一类问题，通过对重点模型进行学习，大家可以在实战中做到举一反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 倒序更新；若正序，同一物品的新状态会被本轮再次读取，悄悄变成完全背包。”
面试官追问
追问 1代码评审里有人把容量循环改成从小到大，声称 Math.max 会自动避免重复选择；用一个重量能被容量容纳多次的物品，结果会发生什么？
结果可能在同一轮多次计入该物品，因为较大容量会读取本轮刚更新的 dp[c-weight]。Math.max 只比较候选价值，并不限制物品使用次数；这段代码的语义已经悄悄接近完全背包，违反每件物品只能选一次的约束。
追问 2商品组合页有数百件候选商品，前端只需计算容量上限内的最大价值，不展示具体清单；你会怎样落地 0-1 背包状态？
可用长度为容量加一的一维 dp 数组，外层逐件遍历商品，内层容量从上限倒序到当前重量。这样每次转移仍读取上一轮语义的状态，并省去完整二维表；若之后要恢复商品清单，仅保留价值数组就不够，需要追加来源记录。
追问 3产品经理把规则改成同一种商品可选任意件，但开发仍坚持倒序容量更新；页面会漏掉哪类最优组合？
倒序更新会让本轮无法复用刚写入的状态，因此同一商品仍最多贡献一次，可能漏掉重复选择该商品形成的更高价值组合。规则变成可重复选取后应改为正序容量更新；代价是模型语义变为完全背包，不能与原 0-1 约束混用。
追问 4线上组合结果异常偏大，日志显示只有一件重量为 2、价值为 3 的商品，容量为 6 时却得到 9；你会先查哪一层循环？
先查容量循环是否从 2 正序走到 6，因为该顺序会依次读到本轮生成的 dp[2] 和 dp[4]，把同一件商品累计三次。修复为从 6 倒序到 2，再用单物品用例回归；若商品本就允许重复，则异常来自需求模型选错。
0-1背包问题是一个基本问题，基于这个基本问题，可以衍生出千姿百态的变种问题，这种题目就非常适合拿来构造解题模型。
0-1背包问题说的是这么回事儿：
有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
注意：每种物品都只有1件
# 思路分析
30 秒速记
- 每件物品只能选一次，状态可定义为容量为
c时前若干物品能取得的最大价值 - 处理完第
i件物品后，dp[c]只代表前i件物品的最优解 - 压成一维后容量必须从大到小遍历，否则本轮刚更新的状态会让同一物品被重复使用
这道题适合用动态规划，因为每件物品只有选和不选两种状态，而直接枚举会产生 2^n 种组合。 可以定义 dp[i][c] 为只看前 i 件物品、容量为 c 时的最大价值，再比较不选第 i 件的 dp[i-1][c]，以及选它后的 dp[i-1][c-w[i]] + value[i]。由于当前行只依赖上一行，二维数组可以压缩成一维数组。压缩后容量必须倒序遍历，确保读取的仍是上一轮状态，避免当前物品在同一轮被重复选中。
← 动态规划入门
