分治
概念
一个复杂的问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）等
分治法使用场景
- 该问题的规模缩小到一定的程度就可以容易的解决。
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
基本步骤
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解
贪心
是指在对问题求解时，总是做出再当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是某种意义上的局部最优解。
选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的局部最优解合成原来解问题的一个解。
适用场景
贪心策略的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法使用的情况比较少，一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析可以做出判断。
应用
小船过河问题
动态规划
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。
适用条件
- 最优化原理（最优子结构性质）：一个最优化策略的子策略总是最优的。
- 无后效性：子问题对主问题的影响可以总结为少数“状态”的特性。某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。即未来与过去无关。
- 子问题的重叠性：子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
