图解你管这叫动态规划

　　闪客：一个楼梯有 10 级台阶，你从下往上走，每跨一步只能向上迈 1 级或者 2 级台阶，请问一共有多少种走法？

　　闪客：对呀，我本来想说假如我告诉你 1+...+99 是多少，你是不是就直接能算出 1+...+100 的值了。

　　小宇：哦你这么一提示我有点感觉了！要想走到第 10 级台阶，要么是先走到第 9 级，然后再迈一步 1 级台阶上去，要么是先走到第 8 级，然后一次迈 2 级台阶上去。

　　小宇：这样的线 级台阶的走法数，就等于走到 9 级台阶的走法数，加上走到 8 级台阶的走法数。

　　闪客：很好，那假如走到第 x 级台阶的走法数我们定义为 F (x)，那你能把刚刚的描述公式化么？

　　闪客：没错，而且不光是 10 级台阶如此，走到任何一级台阶的走法数，都符合这个逻辑，因此就可以得出一个通用公式：

　　小宇：嗯嗯，这样计算 F (10)，只需要知道 F (9) 和 F (8) 就可以了，而计算 F (8)，就只需要知道 F (7) 和 F (6) 就可以了，以此类推。

　　小宇：简单，还是刚刚都逻辑被，想知道 F (2)，只需要知道 F (1) 和 F (0)，诶不对 F (0) 是什么鬼？还有 F (1) 的计算需要知道 F (0) 和 F (-1)，不行呀，这解释不通了。

　　闪客：哈哈，别急，在这道题里，如果只迈到 1 级台阶，那一共就一种走法；如果只迈到 2 级台阶，就只有两种走法。可以直接很直观地得出，没必要推导。

　　小宇：哦哦我懂了，这道题里由于每一个递推项都需要前两项的支持，所以必须有最开头的两项作为已知，就是你说的 F (1) = 1 和 F (2) = 2。

　　闪客：先别急，由于这道题是一道经典的动态规划题，所以我们以这道题为例子来定义动态规划的三要素，在本题中

　　闪客：先别说这些废话了，那接下来你看看能不能写出程序，计算出 F (10) 的结果，这才是难点。

　　闪客：嗯不错，这样很简洁，但复杂度太高了，是 O (2^n)，具体你可以之后想想为什么。现在你看看能不能将复杂度降低。

　　闪客：没错，其实计算新一个阶段的值，只需要一直将其前两个阶段的值保存起来，就可以一直算到最终的结果了。比如定义两个变量 a 和 b 用于存储前两个阶段的值，在计算 F (3) 时。

　　闪客：不错，这就是这道题正确的动态规划解法，而且时间复杂度是 O (N)，空间复杂度是 O (1)

　　闪客：不错，动态规划理解起来不难，难在当需要考虑的因素，也就是变化的维度多起来的时候，有的人就会头脑发蒙，不好找递推公式了，而且这也确实是个难点。

　　如果总重量超过了背包承重，那就不算，或者说将价值记为 0，然后将所有情况中价值最大的那个作为结果。

　　闪客：没错，这个复杂度很高的算法你已经说的很明白了，那接下来你想想看用动态规划思想，能不能解决这个问题。

　　闪客：没错，之前的变量很少所以比较简单，现在变量多了，定义就变得难了起来，我们先来几个定义方便描述。我们将 4 个物品的重量和价值分别表示为：w1，w2，w3，w4，v1，v2，v3，v4。

　　小宇：第二种可能：如果选择不装这个物品 4，那更简单了，就直接等于用一个载重为 5 的背包装前 3 件物品的价值。

　　闪客：没错，而且就只有这两种情况！所以你看看 F (5,4) 是否能用这两种情况的值表示呢？

　　我们的目标就是要计算右下角那个值，即背包载重 W = 5 时，选择前 4 件物品放入背包的最大价值 F (5,4)

　　小宇：好的，F (1,3) 此时背包重量为 1，如果选择放第三件物品的话，诶？好像不行，第三件物品根本放不下呀！

　　闪客：是的，所以这种情况就没必要讨论放第三件物品的情况了，因为根本放不下，因此 F (1,3) 直接就等于 F (1,2)，所以只需要知道 F (1,2) 即可。

　　同理 F (1,2) 也直接等于 F (1,1)，因为在背包重量为 1 时第二件物品也放不下。

　　小宇：显然嘛，现在只有一件物品可以选了，那能放下当然就放咯，所以最大价值就是第一件物品的价值 3，即 F (1,1) = 3

　　闪客：没错，这样我们就找到了一个边界值，小宇你想想看还有哪些边界值可以直接得出？你写在表格里吧。

　　然后第一行也比较好算，背包重量 = 1 时可以放下第一件物品，所以最大价值都等于 3

　　闪客：是呀，不过刚刚我们用的都是具体的数字，那我们试着把这个问题抽象化，用一个载重为 W 的背包，装载 N 件物品，每件物品的重量和价值分别用 wi 和 vi 来表示，那刚刚的状态转移方程是什么呢？

　　闪客：别高兴太早，虽然过程看着清晰了，但代码写起来还是有难度的，你今天回去就把代码试着实现一下吧。

　　本文通过直观演示 01 背包问题的解题思路，简单说明了动态规划思想的算法核心。可能不少人觉得动态规划难在理解，所以花很多时间在理解其思想上。但其实理解核心思想，这一篇文章就够了，更多的是通过不断做题，反过来帮助自己理解动态规划的思想。所以希望读者在读完本文后，和小宇一样，动手将其代码实现，并找来其他变种题目，继续巩固。