分治法
将原问题划分成若干个规模较小而结构与原问题相似的子问题，递归的解决这些子问题，然后再合其结果，就得到原问题的解
特征
- 该问题的规模缩小到一定的程度就很容易解决
- 该问题可以分解为若干个规模较小的相同问题，即问题具有最优子结构性质
- 利用该问题分解出的子问题的解可以合并为该问题的解；
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
动态规划
动态规划适用于分解得到的子问题往往不是相互独立的。
有些子问题会被重复计算多次，动态规划通过记录已解决的子问题，可以避免重复计算。
动态规划通常用于求解最优化问题，在这类问题中可能有多个可行解，最终得到的是其中一个最优解。
步骤
- 描述最优解的结构
- 递归定义最优解的值
- 按自底向上的方式计算最优解的值
- 由计算出的结果构造一个最优解的值
贪心算法
通过做一系列的选择来给出某一问题的最优解，对算法中的每一个决策点，做一个当时（看起来）是最优的选择。这种启发式的策略并不是总能产生出最优解。
步骤
- 将优化问题转化成这样的一个问题，即先做出选择，在解决剩下的一个子问题
- 证明原问题总是有一个最优解是做贪心选择得到的，从而说明贪心选择的安全性
- 说明在作出贪心选择后，剩余的子问题具有这样一个性质。即如果将问题的最优解和我们所做的贪心选择联合起来，可以得出原问题的一个最优解。
版权声明：本文为博主原创文章，欢迎转载，转载请注明作者、原文超链接，感谢各位看官!!!
本文出自：monkeyGeek
座右铭：生于忧患，死于安乐
欢迎志同道合的朋友一起交流、探讨！
monkeyGeek