《算法设计技巧与分析》

沙特版，电子工业出版社

【递归】

归纳法

从求解一个小参数的相同问题开始，把解推广到所有物体。

1. 选择排序：依次选择最小的元素排列到当前队列的最前端。时间复杂度n^2
2. 插入排序：递归，将最后一个元素插入到已排列好的前n-1个元素队列中。
3. 基数排序：将位数相同的数列，保持相对顺序，从最低位依次排列到最高位。
4. 生成全排列：

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!

5. 寻找多项元素：删除两个不同元素后，原来的多数元素仍然是多数元素。

分治

递归地解决每个子实例。

1. 寻找最小元素和最大元素，可以实现只需要3n/2-2次比较。
2. 二分搜索
3. 合并排序：先用mergesort将左右两半排列好，再MERGE两个已经排好的序列。而自底向上排序是：不递归调用mergesort，而是依次以2、4...为分割单位将数组在单位中排列好。时间复杂度nlogn，空间复杂度n。
4. 寻找第k小元素SELECT算法：以分治方法找出中项并以此划分数组，根据k的大小确定继续查找的数组。时间复杂度n。
5. 快速排序：用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]);

6. 最近点对问题：将点依据横纵坐标排列。递归得到左半边和右半边的最小距离。再计算处在临界线左右的点对的最短距离：将这一部分点按纵坐标顺序提取出来，对于其中的每个点计算它之后的7个点距离它的最小距离。将最终得到的三个最小距离取min即可。

DP

自底向上递推（递归）求值。

1. 斐波那契数列
2. 最长公共子序列，不等于最长公共子串（对应的解决方法是画矩阵，横纵坐标相同的点=左上角数字加1，最大元素即子串长度），本问题求法是得到递推式：
   若ai=bi，L[i,j]=L[i-1,j-1]+1
   否则，L[i,j]=max{L[i-1,j]+L[i,j-1[}
3. 矩阵链相乘（用遍历的方法确定矩阵相乘的顺序是不切实际的，通过辅助矩阵C[i,j]来计算，时间复杂度n^3）
4. 所有点对最短路径（FLOYD，三重循环）
5. 背包问题（时间复杂度nC，C为背包容量）

KEYPOINT：寻找递推式（举例得到），每个子序列自身就是最优解。