绪论
最后三章的内容联系前面的贪心算法主要介绍几类算法(问题，思想)，这一章节介绍动态规划。和贪心一样，动态规划不是某个算法，而是一种解决问题的思路，我们在前面介绍过的算法(例如Bellman-ford算法)中就有很多用到这个算法思想的。
事实上在重新讨论了贪心算法的整体思路后，我觉得应该按照介绍最短路算法那里的顺序介绍贪心和动态规划(先介绍动态规划再介绍贪心)。
Dynamic programming
Dynamic programming，也就是我们常说的DP，就是指动态规划，那什么叫做动态规划呢？
课件中以求解Fibonacci数为例：如果我们想要计算出前20个Fibonacci数，求第i个Fibonacci数需要知道第i-1个Fibonacci数和第i-2个Fibonacci数的值，高效的做法是将前i-1个Fibonacci数的值全部存储下来，再求解第i个Fibonacci，而不是在每次求解第i个Fibonacci数时，重复的计算前面i-1个Fibonacci数的值。
Bellman-ford算法求解最短路也是一个动态规划的例子：第k个阶段求解长度为k的最短路径，然后将第k个阶段扩展到第k+1个阶段。
从目的来看，这样设计算法是为了减少求解一个问题中很多子问题(阶段)的重复计算(Bellman-ford算法考虑到了结点最短路径之间的可继承性)，实现时通过将每个阶段的值存储下来从而避免这个阶段重复的计算(用空间换时间)。
结合到框架来看，上述问题都可以划分成若干个阶段，每个阶段求解的过程依赖于前面阶段的解(Bellman-ford算法)或者说可以通过前面阶段的解来减少当前阶段计算的次数(Fibonacci数)，最后一个阶段得到我们整个问题的解(Fibonacci数的第i个阶段为求前i个Fibonacci数)。
满足上述条件的问题我们称为多阶段决策问题，用上述框架设计出来解决该类问题的算法我们称为动态规划方法。
贪心算法和动态规划的区别就在于从某个阶段扩展到后面阶段时，扩展的方向考虑某些经验背景下当前情况的最优解，而放弃其他可能方向的扩展(不讨论所有的可能)。
我们没有介绍(也不会在这个专栏介绍)的分治法和动态规划的区别则在于，分治法的子问题是独立的，且需要子问题合并之后才能得到最终解，而动态规划的阶段是一层一层向外扩展的。
分析贪心算法和动态规划的区别时，我们同时可以知道：设计动态规划算法的策略和框架与贪心算法基本是相同的，除去扩展时根据经验只考虑最优解的一步(如果能证明局部的最优解能够达到实际最优解，那这就是贪心算法了，我是这么看待两个算法的区别和关系的)。
Weighted interval scheduling
贪心法中有一个区间调度问题，这里是“带权的”区间调度问题，每一个区间有一个权值，需要我们求出能够选取的权值和最大的若干个区间(权值全为1时即是区间调度问题)。
朴素的做法是求解出所有的方案，然后求出选取区间的权值之和最大的方案，由于很多compatible方案包含其他compatible的方案，考虑用动态规划算法来进行处理。
我们还是和前面贪心问题例子的推理一样，每次扩展在最右边的区间扩展一个compatible的区间，建立compatible方案之间的联系。
但是我们原本在贪心算法中处理区间调度问题的阶段设定在这里就无法使用了：因为当时的阶段设定建立在选取区间的个数最多为最优的基础上，然而这个问题里选取区间最多绝不意味着选取区间的权值最大。
阶段要建立在选取区间权值最大的基础上，能想到的设定阶段的方案有两种：第i个阶段表示选取序列前i个区间的最大权值；区间前i的长度能够选取的最大权值。
第一个方案的第i个阶段求解选取区间序列前i个区间的最大权值，我们希望阶段能够按照从左往右(从前往后)的顺序扩展，换句话说就是后面阶段的解能够通过前面阶段的解扩展得到，第i个区间如果能够插入，插入的位置应该是前面选取区间的最右边，所以也应该先将区间按照右端点的值从小到大的排序。
将区间按照右端点的值从小到大的顺序排序之后，我们讨论第i个阶段选取区间序前i个区间的最大权值，最大权值有两种可能——不选取第i个区间，继承第i-1个阶段的解；选取第i个区间·······
选取第i个区间时，由于区间是按照序列右端点的大小排序的，但是当我们选取第i个区间时，前面继承的阶段取决于第i个区间的左端点值，即找到前面的阶段中最靠后的阶段对应区间右端点的值小等于第i个区间左端点的值，预处理为每个阶段对应的p值。
p值的计算可以用队列计算，也可以用二分查找来计算。
于是对于第i个阶段，扩展的由来是不选取第i个区间的第i-1个阶段的解，和选取第i个区间继承p[i]阶段的解和第i个区间的并集的解的较优解。
该方案的复杂度为O(nlogn)。
第二个方案的第i个区间求解区间前i的长度能够选取的最大权值，第i个阶段的解除继承第i-1个阶段的解之外，还需要讨论选取以i作为右端点的区间继承其他阶段解的并集的情况，从实现的复杂度来看不是很好的做法。
由此可以看出阶段的划分能够决定最后算法能否实现和实现的效率。
House coloring problem
将n个房子放置成一排进行染色，相邻的房子不能染成相同的颜色，对于第i个房子，染成不同的颜色有其对应的代价，求解将所有房子按照要求染色最小的代价。
朴素的做法是考虑将所有的染色方案解出，求出最小的染色代价，对于很多染色的方案，两两之间是存在重叠的，例如上面的染色方案，如果最后一个房子染成红色，能得到一种新的染色方案，但是这个新的染色方案和上面的染色方案，有大量的代价值的计算是一样的，后面的两种不同方案相当于规模为5个房子的一种方案的扩展。
于是按照房子的个数初定出我们这个问题采用动态规划算法的阶段：第i个阶段表示染色前i个房子的最小代价，但是这么设定有个问题，就是当我们从第i个阶段到第i+1个阶段扩展时，由于规定了相邻房子的染色不能相同，也就是说扩展的方向和结果取决于第i个阶段最后一个房子的颜色，我们需要将第i个阶段再划分成若干个阶段，分别表示染色前i个房子，最后一个房子指定为某个颜色的最小代价。
于是对于某个阶段某个颜色的解，继承于上个阶段其他颜色的最优解与当前阶段染色代价的和。
Maximum subarray problem
给定一个长度为n的实数序列，希望你找到元素和最大的连续子序列。
朴素的做法同样是一对一对首尾元素的枚举，枚举的结果有大量的计算是重叠的，和上一个问题一样能够想到设定第i个阶段求解以第i个数字作为最右数字的最大子序列。
对于第i个阶段的解，它继承第i-1个阶段的解和第i个数字的并集和第i个数字的较优解。
不过这是这类问题最简单的一个问题，这个问题翻译下来是最大子阵问题：如果对象不是一个序列，而是一个矩阵，需要你求解元素之和最大的子矩阵呢？
Segmented least squares
给定若干个点，需要你求出一条直线使得该直线与各点的squared error值之和最小。
设定第i个阶段求解前i个点的最小squared error之和和直线的a，b值，对于第i个阶段，继承前面第j个阶段的最优解与第j个点到第i个点SSE值的并集(c是一个自己设定的常数)。
(不要为啥这个问题介绍的这么草草，问就是想不明白怎么处理的这个问题)
Knapsack problem
最经典的背包问题来了。
给定一个可以容纳一定重量的背包，和n个有单独价值和重量的物品，希望你求出在背包能够容纳的重量范围内能够选取最大代价的物品(每个物品仅能选一次)。
朴素的做法依旧是讨论出所有的方案，但是这些方案依旧有重复计算的部分。
如果我们以选取前i个物品的最大价值作为第i个阶段和第i个阶段的解，这显然不行，因为没有上限的重量，最终不能描述出我们问题需要的答案。
那我们做一点修改：以选取前i个物品且重量不超过W的最大价值作为第i个阶段和第i个阶段的解，那对于我们第i个阶段的解，如果我们不选取第i个物品，继承i-1个阶段的解，如果我们选取第i个物品，这个时候会出现一个问题，第i个物品存在重量，前面阶段的解的背景也是物品总重量不大于W，前面阶段的解和第i个物品的并集不能保证总重量不大于W。
那如果我们记录每个阶段最优解的重量呢？那还是存在问题：前面阶段的最优解不如后面阶段的一个普通解，第i个阶段在选取第i个物品的情况下不是继承某个阶段的最优解而是继承某个阶段的一个普通解。
就是说第i个阶段在选取了第i个物品时，它确实是会继承前面阶段的解，但是这个解不是某个阶段的最优解，因为继承的解要加上第i个物品，它的重量不是小于等于W，而是小于等于W-w[i] (第i个物品的重量)。
于是可以和房屋染色问题一样，将第i个阶段划分成若干个阶段，第(i，w)的阶段表示选取前i个物品重量不大于w的最大价值。
于是第(i，w)个阶段继承不选取第i个物品，第(i-1，w)个阶段的解和选取第i个物品，第(i-1，w-w[i])个阶段的解的较优解。
上一章节的硬币兑换问题就是每个物品重量都为1的背包问题。
总结
动态规划算法和贪心算法的设计框架几乎是一样的：先考虑朴素算法，根据朴素算法之间重复计算的值设定阶段，然后推导阶段与阶段之间是如何扩展(联系)的)(贪心算法考虑局部的最优，扩展方向往往唯一，相当于牺牲了准确率减少计算的次数)。
阶段的设定，扩展必须符合问题的背景，同时保证继承的一定确定是前面阶段的最优解，即前面最优解与当前阶段的决策不会违反当前阶段的规定且确定是当前阶段的最优解，如果发现一个阶段继承的不是前面阶段的最优解，可以考虑将每个阶段根据解的其他属性划分成更小的阶段，转化成更小阶段的最优解继承之前更小阶段的最优解。
比起知识点，更重要的是理解自己在做的问题和相信自己做的每一步吧。
