动态规划和贪心算法小结
（动态规划）彻底搞懂0-1背包
动态规划：
动态规划应用于子问题重合的情况，不同的子问题具有相同的子子问题。
动态规划算法将每个子问题求解一次，将其解保存在一个表格中，需要时进行调用。
- 刻画一个最优解的结构特征。
- 递归的定义最优解的值。
- 计算最优解的值，有自顶向下和自底向上的方法，通常采用自底向上的方法。
动态规划算法的基本要素：
最优子结构：问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
重叠子问题：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看一下结果。
备忘录方法：备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
一、DP思想：
1、把一个大的问题分解成一个一个的子问题。
2、如果得到了这些子问题的解，然后经过一定的处理，就可以得到原问题的解。
3、如果这些子问题与原问题有着结构相同，即小问题还可以继续的分解。
4、这样一直把大的问题一直分下去，问题的规模不断地减小，直到子问题小到不能再小，最终会得到最小子问题。
5、最小子问题的解显而易见，这样递推回去，就可以得到原问题的解。
贪心算法：
每一步都做出当时看起来最佳的选择，也就是说，它总是做出局部最优的选择。
贪心算法的设计步骤：
1.对其作出一个选择后，只剩下一个子问题需要求解。
2.证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3.剩余子问题的最优解与贪心选择组合即可得到原问题的最优解。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解，但通常能获得近似最优解。
联系：
1.都是分解成子问题来求解，都需要具有最优子结构
2.所有的贪心问题都可以用动态规划来求解，可以这么说，贪心算法是动态规划的特例。
区别：
1.贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解则不作保留；
动态规划：全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有的局部最优解
也就是说，假如你要求第十步的最优解，那么第十步的最优解肯定与第九步的最优解有关，而第九步的最优解肯定与第八步的最优解有关。可以这么理解，贪心算法第十步的最优解得把前面九步的最优解都用上了，但是动态规划你需要求第十步的最优解，这个最优解可能只与第八步，第三步，第一步有关，与第九步没有关系，我们为什么选择第八步而不选择第九步呢？是因为我们在计算第十步的最优解的时候其实把1-9步的组合的情况都计算了，选择了其中最优的解，也就是第八步的解，其实第十步解的构成与第九步没有关系，动态规划相当于穷举了1-9步最优情况下的组合，选了其中最优的作为第十步的最优解，而贪心算法第十步的最优解肯定是由第九步构成的。
求一个问题的最优解相当于遍历所有的子集来找最优解，但是这样解随着解空间的维度成指数增长，动态规划其实就是一种遍历，但是他是带备忘录的遍历，我前面算到的子问题，到这儿我不在计算，我直接调用之前保存的值，这样就节省了大量的时间。
2.动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。
3.根据以上两条可以知道，贪心不能保证求得的最后解是最佳的，一般复杂度低；而动态规划本质是穷举法，可以保证结果是最佳的，复杂度高。
