在上一节，我们掌握了求解动态规划问题的通用套路。但正如我们前面所说，通用思路存在一定的局限性——它提供给大家的毕竟是一种方向性的引导，至于能不能实实在在地用自己的双手解决掉一道具体的题目，更多还是看同学们自己的“造化”。
所谓“造化”，其实并不神秘，它就是指我们自己对题目和知识点的思考深度和吸收程度。“造化”是否到位，并不取决于天赋，而是取决于每一位同学自身对题目的量的积累和对解题技术的总结。
作为对通用解题套路的补充，本节笔者基于自己接触过的海量动态规划真题，结合个人对面试命题倾向的观察和思考，提取了两个学习性价比极高的重点解题模型。 模型可以帮助我们迅速地识别并解决掉一类问题，通过对重点模型进行学习，大家可以在实战中做到举一反N，大大提升我们做题的效率和专业程度。
# 0-1背包模型
0-1背包问题是一个基本问题，基于这个基本问题，可以衍生出千姿百态的变种问题，这种题目就非常适合拿来构造解题模型。
0-1背包问题说的是这么回事儿：
有 n 件物品，物品体积用一个名为 w 的数组存起来，物品的价值用一个名为 value 的数组存起来；每件物品的体积用 w[i] 来表示，每件物品的价值用 value[i] 来表示。现在有一个容量为 c 的背包，问你如何选取物品放入背包，才能使得背包内的物品总价值最大？
注意：每种物品都只有1件
# 思路分析
这道题如果全靠本能来做，相信不少同学会联想到“暴力枚举法”：暴力枚举每一件物品放或者不放进背包的情况。考虑到每一种物品都面临“放”和“不放”两种选择，因此 n 个物品就对应 2^n 种情况，进而会带来高达 O(2^n)的时间复杂度。这个时间复杂度是众多复杂度中相对来说比较恐怖的“指数量级”，我们是万万不能让这种东西出现在面试题解中的，因此果断放弃它。
现在我们放弃本能，回归理智，开始调度自己的智慧来做题：这道题最后问了“如何才能使背包内的物品总价值最大？”，我们前面讲过，遇到最值问题，一定要在可能的解题方案中给动态优化留下一席之地。事实上，背包系列问题，正是动态规划的标准对口问题。
下面我们基于通用解题思路来梳理一下这道题：
“倒推”法明确状态间关系
现在，假设背包已满，容量已经达到了 c。站在c这个容量终点往后退，考虑从中取出一样物品，那么可能被取出的物品就有 i 种可能性。我们现在尝试表达“取出一件”这个动作对应的变化，我用 f(i, c) 来表示前 i 件物品恰好装入容量为 c 的背包中所能获得的最大价值。现在假设我试图取出的物品是 i，那么只有两种可能：
- 第 i 件物品在背包里
- 第 i 件物品不在背包里
如果说本来这个背包中就没有 i 这个东西，那么尝试取之前和尝试取之后，背包中的价值总量是不会发生变化的。：
f(i, c) = f(i-1, c)
但如果背包中是有 i 的，那么取出这个动作就会带来价值量和体积量的减少：
f(i, c) - value[i] = f(i-1, c-w[i])
把这个减法关系稍微转化一下，变为加法关系：
f(i, c) = f(i-1, c-w[i]) + value[i]
可以看出，想要求出 f(i, c)，我们只要定位到正确的 f(i-1, c) 和 f(i-1, c-w[i]) + value[i] 的值，并且取出两者中较大的值就可以了。如此，我们便明确出了这道题的状态转移关系。现在我们需要思考的是如何把这种关系用代码的形式表达出来。
首先，基于上面的分析，我们抽取出自变量和因变量：自变量是物品的索引（假设为i）和当前背包内物品的总体积（假设为 v），因变量是总价值。我们仍然是用一个数组来记忆不同状态下的总价值，考虑到这道题中存在两个自变量，我们需要开辟的是一个二维数组。现在我利用二维数组来将上述的状态关系编码化：
dp[i][v] = Math.max(dp[i-1][v], dp[i-1][v-w[i]] + c[i])
以上便是这道题对应的状态转移方程。你会发现我前面真没忽悠你——只要能够利用“倒推”法明确出状态转移关系，我们根本没有必要去构造一个完整而复杂的树形思维模型，直接把状态转移方程往循环里塞就行。
为什么我这么笃定？别忘了，动态规划的关键特性就是“最优子结构”（对这个概念感到模糊的同学，赶紧回到上一节去复习一下）。这道题符合最优子结构的特征——dp[i]只和它之前的状态dp[i-1]有关。最优子结构允许我们推导一次就知晓全局，就是这么爽。
现在我们来瞅瞅这个状态转移方程怎么往循环里塞才合适。仍然是从变量入手：变量是 i 和 v，但本质上来说 v 其实也是随着 i 的变化而变化的，因此我们可以在外层遍历i、在内层遍历 v。明白了这一点，我们就可以编码如下：
