动态规划
之所以叫**动态**规划，是因为该方法将问题分解为一个一个的阶段，每个阶段都有各自的状态，由特定的状态转移方程将当前的状态推到下一次的状态。于是可以看出来，在每一个阶段都有相应的”决策“去选择接下来的状态，所有阶段的决策排成一个序列，我们称它为策略。这种分阶段不断进行状态转移的问题，我们称之为动态规划问题。
是运筹学里的概念，更多的是对于问题性质的总结归纳。而在实际的编程，就像算法导论里讲的那样，是具有最优子结构和重叠的子问题。所谓最优子结构是指原来的总体可以”划分为多个子问题的最优组合，并且子问题可以求解“。重叠的子问题是指在前面不断递归寻找最优子问题时，会不断碰到一样的子问题。这里不理解没关系，下面我会具体。
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。
首先我们来看，如果破解要遍历多少种方法。因为每两英寸之间都可以切割，它们有两种选择，被切割或，于是需要遍历2^(n-1)次，无法。
要求rn的最大值，而现在假设已经知道i从1到n的rn-1的最大值，只需要拿pi+rn-i各自加起来再比较就可以知道rn的最大值了。而要知道rn-1的最大值，也是同样的道理。最后会递归到长度为0,返回0就行了。
要知道r1的最大值，可以直接返回p1;要知道r2的最大值，需要比较p1+r1和p2+r0（r0的值为0）;……这样把所有的情况都比较得出来后，就可以知道rn的最大值了。
这里将rn分解为pi+rn-i，并假设rn-i也是最优的方法，就是我开始说的”最优子结构“：先在所有”最优子结构“里找到各自进行”状态转移“后的最优值，再递归地求解最优子结构。
这个可以理解为把那个树的图压缩成的东西，压缩掉的是那些重复计算的径。每个定点都是一个子问题，子问题的求解时间则是射出去的边的总数。所以这时问题的时间复杂度变成了O(n(n+1)/2)，化简为O(n^2)。
1.有最优子结构也可能可以使用算决（事实上能使用算法的问题绝大多数都能使用动态规划）。
2.子问题互相之间必须是无关的，比如求最长径时遇到了环，不同的子问题都有重复的中间节点，这样分解出来的子问题就都是相关的，便不能使用动态规划解决。
大家应该都知道算法是每个阶段都追求局部的最优，然后达成全局的最优，必须要证明这样的合才能使用算法，因为大部分情况下全局的最优每个阶段都不一定最优。
像这里的部分背包问题可以使用反，假设当前背包里的物品价值已达到最高，而且没有每磅价值最高的物品，那么可以移除当前背包里价值最低的物品，并放入价值最高的物品，则背包的价值提升，金字旁的女孩名字与假设矛盾。于是这个问题可以每一次都拿当前价值最高的物品而得到整体价值的最高。
这里默认大家都懂这算法了。事实上这个算法就是典型的算法，但这种问题也往往是动态规划里的入门示例（我的运筹学动态规划的例子就是这个）。
一个图中的点分为两个集合，一个是V：所有点的集合；另一个是S：表明已经找到最短径的点，即一个点找到了最短就加入S，而我们要证的就是加入S的点的最短都已确定。设d[u]表示u点到源点的当前距离，z[u]表示u到源点的最短。
和证明整数的唯一分解有些类似，假设一个点u是加入S集合中的第一个不满足d[u]=z[u]的点，如果u点到源点s没有，那么d[u]=z[u]=无穷，就不满足z[u]=d[u]这个条件了，所以可以得出s到u一定有条最短。我们假设y点是V-S中的一点，y-u不一定存在，也就是说y有可能就是u点，然后假设x是y的紧邻前驱，但s-x也不一定存在，s点有可能为x点，因为x已经加入S了，x又是y的紧邻前驱，所以在松弛时已经计算出d[y]=z[y]，（因为图中的s-u是一条最短了，所以此上的s-y也是s到y的最短，否则s-u就不是s到u的最短了）（根据性质：（此中的字母与本文无关，只是描述性质用到）s-u-v是图G某u点,v点属于V的最短径，而且在松弛边（u，v）之前的任何时间d[u]=z[u],则在操作后总有d[v]=z[v]），到了这里我们就得出了两个不等式，1.在这条径中看得出d[u]=z[u]=z[y]=d[y]，2.在选择u点时，只有d[u]=d[y]时，才会选到u点加入S，从而得到d[u]=d[y]=z[u]=z[y]。
我们能看到，这个问题的式子本身是很直观的线性规划问题，假如求最大值的表达式没有二次方，则可以直接用高中学习的线性规划知识画图解决。但是这种静态规划问题，可以人为的加入**阶段**的概念，然后用动态规划的思想解决，就像图片里那样。
动态规划应用于子问题重叠的情况。对于公共子问题，分治算做很多不必要的工作，它会反复求解公共子问题。而动态规划算...
目录 动态规划与分治法 2.动态规划求解的最优化问题应该具备的两个要素2.1 最优子结构2.2 子问题重叠 动态规...
1. 概述 动态规划与分治法相似，都是通过组合子问题来求解原问题。区别在于，分治法将问题划分为互不相交的子问题，递...
状态转移方程 从之前某个阶段的某个或某些状态状态到下一个状态之间的关系式，就叫做状态转移方程。 最优子结构 每个阶...
@你：本文最后有一小碗儿鸡汤，如果你没有增肌需求，又点开了推送，可以直接滑到最下给自己洗。阅读本文需要3分钟。...