图解你管这叫动态规划

于:Flash，最近在学动态编程，就是想不通你能告诉我一些关于它的情况吗

闪电侠:没问题我很擅长这个首先说一下动态编程你首先想到的是什么

于:就是什么子问题，状态转移方程乱七八糟的哦，不，不，不当我想到他们的时候我的脑子又嗡嗡作响

闪电侠:别急，把所有名词都忘了，听我说。

于:好吧，说吧。

修卡:小雨，我问你，1到100是多少。

1 + 2 + 3 + ...+ 100 = 。

于:5050！

修卡:你为什么不遵循常规呢你应该说你不知道

于:我不能假装我不知道，即使我已经说了太假了

全剧结束...

闪电侠:好，那我再给你一个问题。

于:好吧，说吧这次我肯定不知道

闪电侠:一个楼梯有10级台阶从下到上每一步只能走1到2步有多少种方式

于:嗯，我真的不知道让我考虑一下

于:我做不到我真的不明白我想着后面，忘了前面

闪电侠:你还停留在疲惫的思想里仔细想想我给你的第一个问题，看看你有什么想法

于:啊！所以有关联。

Flash:是的，我正要说如果我告诉你什么1+...+99，你能直接计算出1+的值吗...+100。

于:哦，我觉得有点像！想走到第10步，要么走到第9步再走一步，要么走到第8步再一次走两步。

闪电侠:太好了！你找到感觉了！继续说。

于:这样的话，走到第十步的次数等于走到第九步的次数，加上走到第八步的次数。

Flash:很好，那么如果我们把走到X步的步数定义为F，你能把刚才的描述公式化吗。

于:那太简单了。公式是:

F = F + F

Flash:没错，而且不仅仅是10个步骤。任何一步的移动次数都符合这个逻辑，所以可以得出一个通用公式:

F = F + F

于:嗯像这样计算F，只需要知道F 和F ，而计算F ，只需要知道F 和F ，以此类推

闪电侠:没错然后想想F和F 怎么算

于:简单，或者说只是符合逻辑如果想知道F，只需要知道F 和F 呃，F 到底怎么了另外F 的计算需要知道F 和F ，这个没法解释

修卡:哈哈，别担心在这个问题中，如果你只达到第一步，就会有一条路要走如果你只走了2步，那就只有两条路可以走可以直接直观的得到，不需要推导

于:哦，哦，我明白了在这个问题中，由于每个递推项都需要前两项的支持，所以前两项必须已知，即F = 1，F = 2

闪电侠:没错。

于:嗯嗯，感觉这样就把结果都推出来了！我写程序给你看看。

Flash:不用担心，因为这个问题是一个经典的动态编程问题，我们以这个题目为例来定义动态编程的三要素。在这个话题中，

和F 称为F 的最优子结构

F = F +F 称为状态转移方程。

F = 1，F = 2是问题的边界。

做了动态规划之后，找到这三个要素就好了。

于:哇，升华了瞬间高了很多

Flash:暂且不说这些废话，然后看看你能不能写个程序，算出f的结果，这才是难点。

于:这好像是编程中的递归问题。简单！

intgetWaysifreturn 1，ifreturn 2，return getWays+getWays，

闪电侠:嗯，是的，很简单，但是太复杂了是o你可以以后再想为什么现在看看你能否降低复杂性

于:我想想计算F时，我们需要计算F 和F ，而递归计算F 时，我们需要计算F 和F ，这样很浪费时间

闪电侠:没错实际上，要计算新阶段的值，只需要保留前两个阶段的值，直到最后的结果例如，定义两个变量A和B来存储前两个阶段的值计算f时

步骤1234...步行a=1b=23

计算F时，F 的值不需要保存，A和B依次替换新值。

步骤1234...10走a=2b=35

依此类推，最后计算f的值。

步骤12...8910步行a=34b=5589

当然，你也可以保留所有之前的值，但这样会增加空间复杂度，具体看你的需求。

于:好吧，那这个代码好写，就这样。

intgetways 2 ifreturn 1，ifreturn 2，inta = 1，intb = 2，int temp = 0，for inti = 3，I = n，i++ temp = a+b，a = b，b =温度，returntemp

Flash:没错，这是该问题的正确动态规划解法，时间复杂度为O，空间复杂度为O

于:哇，这就是动态编程太简单了

Flash:是的，动态编程并不难理解难点在于，当需要考虑的因素更多，也就是变化的维度更多的时候，有些人就会迷茫，很难找到递推公式而且，这确实是一个难点

于:哦，真的吗。

闪电侠:当然，我再给你一个问题。

于:加油，兄弟。

修卡:咳咳，那你仔细听着。

有一个背包，可以背5kg重的物品。

共有4项，其权重和值如下。

那么，在不超过背包重量的情况下，有哪些物品可以放入背包中使总价值最大化呢。

于:我明白了，就是这个背包最多能带走多少钱。

闪电侠:是的。

于:哦，我不能我又陷入了爬楼梯的想法

闪电侠:没关系这个问题想出一个遍历的思路其实并不容易可以先说出来，找感觉

于:嗯，就是每样东西都可以放进背包，也可以不放。

如果总重量超过背包的承载能力，则不计算，或者将数值记为0，然后取所有情况下数值最高的一个作为结果。

这个复杂度也很容易得到，就是o。

闪电侠:没错你已经清楚地表明，这个算法具有很高的复杂性然后，想想自己能否用动态规划的思路解决这个问题

于:好，你之前说动态规划的三要素是最优子结构，状态转移方程和边界。

闪电侠:没错之前变量很少，所以比较简单现在有许多变量，定义变得更加困难为了便于描述，先说几个定义我们将四个项目的权重和值分别表示为w1，w2，w3，w4，v1，v2，v3，v4

如果我们使用

F

表达

用一个负重为W的背包，装下前I项物品的最大值。

主题实际上是

用一个负重5kg的背包，装下前四项的最大值。

事实上，它正在解决

F

你能找到状态转移方程吗。

余:让我想想，就看这第四项，有两种可能:

第一种可能:如果你选择放在背包里，你已经有6元钱了。

此时背包剩余装载量为1kg，剩余物品为去掉第4项后的前三项。

这部分可获得的最大值相当于

用一个负重1kg的背包，装下前三项的最大值。

哇，所以这部分是

F

修卡:哈哈，你自己说得对！

于:所以最后如果你选择把第4项放在背包里，这种情况下，最大值等于两者之和。

F + 6

闪电侠:太好了，小玉另一种情况呢

于:第二种可能:如果你选择不装这个物品4，那就更简单了，直接等于用一个装载量为5的后背来装前三个物品的价值。

F

闪电侠:没错，而且只有这两种情况！所以能不能看看F能不能用这两种情况的值来表示。

于:哈哈，很简单等于这两种情况的最大值

F =最大值F + 6，F

Flash:太好了，现在状态转移方程出来了，这个时候我们来画个表。

我们的目标是计算右下角的值，即当背包载荷W = 5时，选择背包中前四项的最大值F。

于:哇，这张桌子真清晰根据上面的公式

F =最大F + 6，F

也就是说，只需要知道F和F 的值，对吗。

闪电侠:没错然后看f是怎么算的

于:好的，f，这时背包的重量是1如果你选择放第三项，嗯

Flash:对，所以这种情况不用讨论放第三项的情况，因为根本放不下，所以F直接等于F ，所以你只需要知道F 。

同理，F直接等于F ，因为即使背包重1，第二个物品也装不下。

修卡:小雨，想想吧F等于什么

于:很明显，现在只有一个项目可以选择能放下当然能放下，所以最大值就是第一项3的值，也就是F = 3

Flash:没错，所以我们找到了一个边界值小宇，你还能直接想到什么边界值把它写在表格里

于:好的，首先第一列是背包重量为0时的情况显然什么都不能装，所以都是0

然后第一行也很好算，背包重量gt，= 1可以放下第一项，所以最大值等于3。

闪电侠:很好接下来依次填写表格中的所有项目，自然就可以算出F了

于:哇，好清晰啊！

Flash:是的，但是刚才我们用了具体的数字，所以我们试着抽象一下这个问题我们用一个负重为W的背包装载N件物品，每件物品的重量和价值分别用wi和vi表示刚才的状态转移方程是什么

于:emm，刚才F = max F +6，F ，如果全部用变量表示，就是

F =

最大F + vn，F

Flash:很好，这是状态转移方程。

和F 是F 的最优子结构。

而刚才表格中的第一行和第一列，即F和F，都是边界值！

于:哇，我爱你，飞侠！终于明白动态编程的思想了！

闪电侠:别太高兴了虽然流程看起来很清晰，但是写代码还是很难今天回去尽量实现代码

于:好的，保证完成任务。

修卡:快到晚饭时间了旁边新开了一家饺子馆你想加入我们吗

于:哦，不，我想利用晚上吃饭的时间消化一下动态编程的知识我不用实现代码吗

Flash:哦好吧~

附言

本文通过直观演示01背包问题的求解思路，简单说明了动态规划思想的算法核心很多人可能觉得动态编程很难理解，所以花了很多时间去理解他们的想法但其实要理解核心思想，这篇文章就够了更多的是通过不断做题来帮助自己理解动态规划的思路所以，希望读者看完这篇文章后，和小鱼一样，开始实现它的代码，找其他变体标题继续巩固