开篇，想讨论讨论我最喜欢的动态规划。

动态规划的思想

以多阶段决策的思路去 优化 组合问题的遍历过程，每一个问题得到的最优解均可以用来求解全局最优解。动规的正确性依赖于“一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列”。（前面一句话是自己总结的，如果不准确请在评论区拍砖，后面这句话我自己尝试总结了半个小时，都感觉描述不对，最后从我看过的一本《算法设计》上面摘录了，后面我称之为“原则”）。

这句话再打开看一下。首先其本质还是一个遍历，当然算法所解决的大部分的问题都是在提升遍历的性能。

那么怎么优化呢，利用多个阶段决策的思路，也就是说，并不遍历全部解空间，由于条件1的存在，我们只需要保证将一个问题分解出子问题即可，因为子问题如果最优了，那么最终问题也是最优的。

怎么理解“任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列”这句话呢？我相信绝大多数人没有用好动规，第一步就是卡在这个原则的理解上了。

我先举个例子，以爬楼梯这个过程来看，一个楼梯如果有n个台阶，而人的腿或长或短，反正一次最多能跨N个楼梯，心情好多跨几个，心情不好少跨几个，那么，最后一步跨几个楼梯和在最后一步之前走楼梯的方式之间是否有关呢（忽略体力、时间、情绪等因素，我们仅考虑一步跨几个楼梯这个过程）？可以想象一下这个过程。答案是不相关的，最后一步要跨过几个楼梯的“决策”并不受前面的决策的影响。这个就是对动规条件的直观理解，最后一个决策并不受前面一个决策的影响。但是需要区分清楚，最后一个决策可能是有多个情况的，比如可以跨1个跨2个跨3个，以及到n个。但是这仅仅是子问题划分的不同。所以一定要区分清楚“子问题划分不同” 和 “前面决策是否影响后面决策” 。

再举个反例。小朋友和父母有个约定，过年的压岁钱如果不足100，就可以自己花，但是如果一天给的压岁钱超过了100，就要上交，存下来以后上学用，当然，小朋友可以选择接受或者不接受某个人的压岁钱。于是，上午来了四个阿姨，每人给了20，这样就有80，小朋友特别开心。然后，晚上睡觉前一分钟突然又第五个阿姨来了，又给了20，结果凑够100，这时候满足条件就要上交。所以小朋友就会想，您这一来，把我一天的决策都否了。。这个事情抽象一下，本来接受前面几个阿姨的零花钱是最优决策，但是当第五个阿姨来的时候，导致了前面决策最优性对全局而言失效了。这个问题也是一个多阶段决策问题，但是动规是不合适的。这类问题的具体解法，以后会有讨论。

动规的思想还是比较直观的，只要理解遍历、最优子问题、“动规原则”，就充分理解动规的思想了。

问题求的过程，就转化为如何将全局问题转化为子问题了。

动态规划问题的典型代表

教科书上面的动规问题代表如下：多点到多点的最优路径、矩阵链乘法、投资问题、背包问题、LCS、图像压缩、、最优二分检索、RNA最优二级结构等。

这些都是动规的典型代表，其中部分实例，我会用代码实现，部分给出参考资料，有兴趣的大家可以自己去研究。

动态规划的算法设计

动规的算法设计，通透长分为几个步骤，这套方案也是教科书的标准设计。

1）问题建模，确认目标函数和约束条件是什么？

2）子问题的分解以及边界条件

3）推导递推方程，描述优化函数值与子问题的优化函数值之间的关系

4）是否满足动规原则

5）确定最小问题的界定--即最下的哪个子问题是什么，它的优化函数的初始值是什么？

我再以背包问题，详细解读一下每一个步骤具体要干什么

背包问题：一个旅行者随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为、 . 如果背包的最大重量限制是b, 每种物品可以放多个（可以放多个，不同于0-1背包问题），怎样选择放入背包的物品以使得背包的价值最大?

step1

需要用目标函数来描述某一问题中变量与结果之间的关系。如果数学符号记得，可以用数学表达式表示，如果数学符号不记得了，至少要想清楚该问题中目标函数。

问题1中变量是i，与变量相关的直接参数是wi，vi，限制条件是b，所要求的是最大利润，我们假设为大P，以上几个参数是题设中已经明确指出的，但是还有另外一个隐含参数，就是每一个物品装入的个数Ki，即第i个物品装了ki个。即我们需要一个函数来描述P与wi、vi、b，ki之间的关系。这个就叫目标函数。

我们来直观的想一下，P应该是一个“和函数”，即一系列vi*ki的加和，而限制vi和n的具体值的，则是wi*ki和b。所以很直观的可以得到这个目标函数

以及约束函数

如果该问题是0-1背包问题，则。

step2：

已经确认目标函数后，子问题也迎刃而解。既然目标问题是从1到n，那么子问题自然可以分解成用从1到n-1，进一步从1-n-2，所以子问题就变成了上述问题从1到k，k=1,2,3……n的问题。k最小是到1，最大是到n。我想到这里，应该有点感觉了。这不就是一个for循环吗？分别计算出从1-n针对目标函数的最优解。soga，这下理解为何最开始要先相处目标函数了吧。

ps：关于分解子问题时，从n开始向n-1分解，就是将大规模的数据分解成更小规模的数据。是子问题分解的直观手段。

step3：

确认了子问题和目标函数后，我们会发现对于第k个物品来讲，可能存在2个情况：

1）假如不把k放进去，则剩余重量不变

2）假如把k放进去，而且要放n个，(1，)，则剩余质量需要减去放入n个k的重量。

我们去两种情况里面最大的不就可以了。即前K个物品，剩余重量不超过y，它的最优解计算如下：

{}

假如这个问题符合动规原则，那么这个表达式从1开始计算，当计算到n时，也就得到了全局的解了。

这一步的推到在具体问题中，是最难的一环。有一个比较好的方法，就是先从实例开始，从互具体问题的n到n-1，再到n-2去手动计算找规律，找完规律后，在用更大的n去验证一下规律的正确性。具体的规律还是要在具体的问题中多体会，后续的blog我会把动规现有的大部分典型问题，都专项分析一下表达式推到的过程。

ps：这个表达式内部是有减法的，从程序角度而言，一旦看到减法，必然要针对减法的地方设计边界。其中k-1的边界必须大于0，表示至少有一个物品。y的边界必须大于0，表示重量不可以为负数。这个边界就是终止循环条件的关键了。

step4：

上面的分析，看起来毫无瑕疵，但是我有一个直觉：某一个物品是否能被放入，必然是受前面的物品是否被放入以及被放入物品的质量所决定的。至少我当时是这么想的。

再来看看这个想法是否对呢？

经过前面的step2，step3，我们已经知道子问题就是第k个物品以及重量y之间的关系，那么第y个物品能否被放入是否受前面y-1个物品影响呢？必然是影响的，这个毫无疑问，但是影响的点在哪呢？在总重量的限制。既然如此，我们在划分子问题的时候，我们就做一个特殊处理：预留足够的重量空间给第K个物品。这样第k个物品是否能够被放入这件事就与前k-1个问题无关了。解了这个坎，心里就踏实了

对应动规的原则，一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。前k-1个物品的最优解一定是在第k个物品没有参与之前的全局最优解，而前k个物品的最优解也是k参与以后重新计算的，也是k+1物品没有加入之前的最优解。

所以这个问题是满足动规原则的。

step5：

初始条件，初始条件是结束递归和循环的条件。在该问题中，可以理解为第1个物品，重要为1的情况。

代码设计

根据step3的方程，我们可以看出，需要一个二维数组（用于记录f（x，y）的全部解空间），两个一维数组（v、w和i的对应关系）以及n个相关变量。

理解算法和动态方程以后，实现的过程中，只要注意到边界条件和n的计算即可。

上述实现只能计算出最大值，但是不能得到物品的放入情况。从工程上来讲，我们不仅想知道结果，更想知道最终的物品放置情况。

那就还需要设计一个二维数组，用来跟踪物品k被放置的次数。我们称之为标记函数。

用trace(k,y)来表示当重量为y的时候，放入物品k的情况，对应动规方程f(x,y)。

标记函数的实现，放在后面blog中讨论。

代码实现

简书代码编写需要markdown模式，但是markdown模式对公式编辑支持不好，所以代码实现放在另外一个blog。

https://www.jianshu.com/p/0f7cea74bd9d

总结

背包问题只能说是动规的一个典型代表，他也是动规里面最简单的实例，试图用这么一个问题来说明动规的方法论。大多数实际问题，都比这个问题涉及的因素要多，例如背包问题实际上除了重量和价值以外，还会涉及到体积、物品的外形规则（长条状、还是方形的）等多种因素，那么单纯的一个二维数组是无法满足计算的，可能需要引入矩阵运算或者状态管理。但无论复杂的问题总可以被分解成各种子问题的组合方式。工作如此，生活亦如此。关于动规的思想在工程里面的应用，我会在后续的blog中寻找实际问题及其解决方案再来讨论。