动态规划与贪心、分治的区别
贪心算法(Greed alalgorithm) 是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致全局结果是最好或最优的算法。
分治算法(Divide and conquer alalgorithm) 字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
动态规划算法(Dynamic programming，DP) 通过将原问题分解为相对简单的子问题的方式来求解复杂问题。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
贪心法在处理每个子问题时，不能回退，而动态规划可以保存之前的结果，择优选择。下面针对Interval Scheduling 问题，分析动态规划在实际问题中的应用。
Interval Scheduling 问题如下图所示，每个长条方块代表一个工作，总有若干个工作a、b... h，横坐标是时间，方块的起点和终点分别代表这个工作的起始时间和结束时间。
当两个工作的工作时间没有交叉，即两个方块不重叠时，表示这两个工作是兼容的(compatible)。
当给每个工作赋权值都为1时，则称为 Unweighted Interval Scheduling 问题；当给每个工作赋不同的正权值时，则称为 Weighted Interval Scheduling 问题。
问题最终是要找到一个工作子集，集合内所有工作权值之和最大且集合内每个工作都兼容。
对于 Unweighted Interval Scheduling 问题，使用贪心算法即可求解，具体做法是按照结束时间对所有工作进行排序，然后从结束最晚的工作开始，依次排除掉与前一个不兼容的工作，剩下的工作所组成的集合即为所求。
然而，对于 Weighted Interval Scheduling 问题，贪心法找到的解可能不是最优的了。此时考虑使用动态规划算法解决问题，兼顾权值选择和兼容关系。
定义P(j)1、首先依然按照结束时间对所有的工作进行排序；
2、定义p(j)为在工作j之前，且与j兼容的工作的最大标号，通过分析每个工作的起始时间和结束时间，可以很容易计算出p(j);
3、例如下图所示，p(8)=5，因为工作7和6都与8不兼容，工作1到5都与8兼容，而5是其中索引最大的一个，所以p(8)=5。同理，p(7)=3,p(2)=0。
1、定义opt(j)是j个工作中，所能选择到的最佳方案，即opt(j)是最大的权值和；
2、对于第j个工作，有两种情况：
case 1: 工作j包含在最优解当中，那么往前递推一步，j之前能选择到的最优解是opt(p(j))，即
case 2: 工作j不在最优解中，那么从j个工作中选取解集和从j-1个工作中选取解集是一样的，即
3、当j=0时，显示结果为0，这是边界条件。
后一步的结果取前一步所有可能情况的最大值，因此综上所述，能得到动态规划的递归关系为：
1、递归法
递归会使得空间复杂度变高，一般不建议使用。
2、自底向上法
从小到大进行计算，这样每次都可以利用前一步计算好的值来计算后一步的值，算法时间复杂度为O(nlogn)，其中排序花费O(nlogn)，后面的循环花费O(n)。
Knapsack Problem 问题 背包问题的定义如下图所示，给定一个背包Knapsack，有若干物品Item
每个item有自己的重量weight，对应一个价值value
背包的总重量限定为W
目标是填充背包，在不超重的情况下，使背包内物品总重量最大。