分治 Divide and Conquer
将问题划分为互不相交的子问题。递归地求解子问题的解，再将这些解组合起来，得到原问题的最优解。（eg. 归并排序算法 $T(n)$）
- 分解原问题为若干子问题，这些子问题是原问题的规模较小的实例。
eg. 分解带排序的n个元素的序列成各具n/2个元素的两个子序列。 - - -$D(n)=\theta (1)$ - 解决这些子问题。
如果子问题规模足够小（基本情况），就直接求解，否则（递归情况）使用递归进行求解。
eg. 使用归并排序递归地排序两个子序列。 - - -$2T(n/2)$ - 合并这些子问题的解获得原问题的解。
eg. 合并两个已排序的子序列以产生已排序的答案。 - - -$C(n)=\theta (n)$
将原问题划分为a个问题，每个问题的大小是n/b：$T(n)=aT(n/b)+D(n)+C(n)$。
递归式：一个等式或不等式，通过更小的输入上的函数值来描述一个函数。（用自身定义自身）
求解递归式的方法：
- 代入法 Substitution 猜测解的形式，减少不确定范围，用数学归纳法求出解中常熟并证明这个界是正确的。
$T(n)=2T(n/2)+n\to T(n)=O(nlgn)$
$T(n)=T(n-1)+n\to T(n)=O(n^2)$
$T(n)=T(n/2)+1\to T(n)=O(lgn)$ - 递归树法 Iteration 将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
- 主方法 Master 对于递归式 $T(n)=aT(n/b)+f(n)$：
a. 若对于某个常数 $\epsilon >0$ 有 $f(n)=O(n^{log_ba-\epsilon })$，则 $T(n)=\theta (n^{log_ba})$。
b. 若 $f(n)=\theta (n^{log_ba})$，则 $T(n)=\theta (n^{log_ba}lgn)$。（适用于分治的递归式）
c. 若对某个常数$\epsilon >0$ 有$f(n)=\Omega (n^{log_ba+\epsilon })$，且对某个常数$c<1$和所有足够大的n有$af(n/b)\le cf(n)$，则 $T(n)=\theta (f(n))$。
动态规划 Dynamic Programming
优化子结构：一个问题包含其子问题的最优解
重叠子问题：利用递归算法反复求解相同的子问题
动态规划算法无后效性，总是能够得到全局最优解。
动态规划算法对每个子问题只求解一次并将其解记录在表格中。任何子问题都会等到它依赖的子问题已经求解结束才会进行求解。动态规划算法运行时间相当于每个子问题的求解时间之和。
- 寻找最优解的特征结构
证明问题含有优化子结构
eg. 最短路径问题具有优化子结构，而最长简单路径问题（不允许成环）不具有优化子结构。根本原因在于求解最长路径子问题时用到的某些资源（顶点），导致这些资源在求解其它子问题时不可用（若两个最长路径子问题旋律共同的顶点则会成环）。
a. 证明问题的最优解的第一个组成部分是做出一个选择。例如选择钢条的第一次切割位置、选择矩阵链的划分位置。做出这次选择会产生一个或者多个子问题。
b. 对于一个给定问题，在其可能的第一步选择中，假定已经知道哪种选择才会得到最优解。
c. 给定可获得最优解的选择之后，确定这个选择会产生哪些子问题，以及如何最好地刻画子问题空间。
d. 证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。（反证） - 递归地定义最优解的值
找到问题规模为n的最优解与规模小于n的子问题的最优解之间的数量关系。 - 计算最优解的值，通常采用自底向上的方法
自底向上方法使得任何子问题的求解只依赖于规模更小的问题的求解，也可以用过自顶向下加入备忘机制来实现。
计算最优解的过程中可以重构解来记录最优解的获取方式。 - 利用计算出的信息构造一个最优解
eg. 最长公共子序列、钢条切割、最优二叉搜索树
贪心 Greedy
优化子结构：问题的优化解包含了子问题的最优解。
贪心选择性(greedy-choice property)：全局优化解可以通过局部优化选择得到。即：进行选择时可以直接做出在当前问题中看来最优的选择而不必考虑子问题的解。即：存在一个最优解是以贪心选择开始的。
证明贪心选择性：先考察一个全局最优解，如果全局最优解可以转换成以贪心选择开始，则已得证，如果不能，则将这个全局最优解的开始替换成贪心选择，从而可以得到一个更优的解。因此全局最优解应该选择这个贪心选择做为第一次选择，从而得到一个规模更小的子问题，通过数学归纳法可证每次都对子问题进行贪心选择可以得到原问题的最优解。
贪心算法并不能保证得到全局最优解。
通过贪心选择性的证明，我们说明了存在一个全局最优解是以贪心选择开始的，但我们没有证明所有贪心选择开始的解都是全局最优解，因此在某些问题上使用贪心算法可能无法得到全局最优解。
贪心算法与动态规划最大的不同在于，贪心并不是首先寻找子问题的最优解然后在其中进行选择（这种选择通常依赖于子问题的解），而是直接做出一次贪心选择（局部最优解）然后求解剩下的唯一子问题，不必求解所有可能相关的子问题。即：贪心算法总是做出局部最优的选择，希望这样的选择可以最终达到全局最优，这种选择可能依赖于之前做出的选择，但不会依赖于任何将来的选择或者子问题的解。
贪心算法通常采用自顶向下的设计：做出一个选择，然后求解剩下那个子问题。而不是自底向上求解出很多子问题再做出选择。每个贪心算法下，几乎总有一个更繁琐的动态规划算法。
- 将最优化问题转化为这样的形式：对其做出一次选择之后，只剩下一个子问题需要求解。
- 证明做出贪心选择后，原问题总是存在最优解，即贪心总是安全的。
进行贪心选择时，可以通过数据预处理（排序）或者使用合适的数据结构（优先队列）来使得贪心选择更快速高效。 - 证明做出贪心选择后，剩余的子问题的最优解与该贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
eg. 最小生成树、Dijkstra算法、赫夫曼编码、任务调度问题、部分背包问题
参考：《算法导论》机械工业出版社 第2、4、15、16章