沙特版，电子工业出版社
【递归】
归纳法
从求解一个小参数的相同问题开始，把解推广到所有物体。
- 选择排序：依次选择最小的元素排列到当前队列的最前端。时间复杂度n^2
- 插入排序：递归，将最后一个元素插入到已排列好的前n-1个元素队列中。
- 基数排序：将位数相同的数列，保持相对顺序，从最低位依次排列到最高位。
- 生成全排列：
perm(m)
if m==n return;
else
for j=m to n
swap(P[j],P[m]);
perm(m+1);
swap(P[j],P[m]);
时间复杂度：nn!
- 寻找多项元素：删除两个不同元素后，原来的多数元素仍然是多数元素。
分治
递归地解决每个子实例。
- 寻找最小元素和最大元素，可以实现只需要3n/2-2次比较。
- 二分搜索
- 合并排序：先用mergesort将左右两半排列好，再MERGE两个已经排好的序列。而自底向上排序是：不递归调用mergesort，而是依次以2、4...为分割单位将数组在单位中排列好。时间复杂度nlogn，空间复杂度n。
- 寻找第k小元素SELECT算法：以分治方法找出中项并以此划分数组，根据k的大小确定继续查找的数组。时间复杂度n。
- 快速排序：用SPLIT将首项放到正确的位置，递归调用处理左半边和右半边。最坏情况：n^2，平均时间复杂度nlogn，不需要辅助存储空间。
SPLIT：
i=low;
x=A[low];
for j=low+1 to high
if A[j]<=x
i++;
if i!=j swap(A[i],A[j]);
swap(A[low],A[i]);
- 最近点对问题：将点依据横纵坐标排列。递归得到左半边和右半边的最小距离。再计算处在临界线左右的点对的最短距离：将这一部分点按纵坐标顺序提取出来，对于其中的每个点计算它之后的7个点距离它的最小距离。将最终得到的三个最小距离取min即可。
DP
自底向上递推（递归）求值。
- 斐波那契数列
- 最长公共子序列，不等于最长公共子串（对应的解决方法是画矩阵，横纵坐标相同的点=左上角数字加1，最大元素即子串长度），本问题求法是得到递推式：
若ai=bi，L[i,j]=L[i-1,j-1]+1
否则，L[i,j]=max{L[i-1,j]+L[i,j-1[} - 矩阵链相乘（用遍历的方法确定矩阵相乘的顺序是不切实际的，通过辅助矩阵C[i,j]来计算，时间复杂度n^3）
- 所有点对最短路径（FLOYD，三重循环）
- 背包问题（时间复杂度nC，C为背包容量）
KEYPOINT：寻找递推式（举例得到），每个子序列自身就是最优解。
