算法

递归与分治

• 分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
• 如果问题可分割成k个子问题，且这些子问题都可解，利用这些子问题可解出原问题的解，此时，分治法是可行的。
• 由分治法产生的子问题往往是原问题的较少模式，为递归提供了方便。

递归

• 定义：直接或间接调用自身的算法
• 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
• 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

常见基础递归算法

常见基础递归算法有：n的阶乘、斐波那契数列、汉诺塔、二分查找、全排列等

//n的阶乘
int fac(int n)
{
	if(n = 0 ) return 1;
	return n*fac(n-1); 
}
//斐波那契数列
int fibonacci(int n)
{
	if (n <= 1) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}
//全排列
//产生list[k:m]的所有全排列
 void Perm(Type list[], int k, int m){
 	//只剩下一个元素
 	if(k == m){
 		for (int i = 0; i < m; i++){
 			cout << list[i];
 		}
 		cout << endl;
 	}
 	
 	for(int i = k; i <=m; i++){
 		Swap(list[k], list[i]);
 		Perm(list, k+1, m);
 		Swap(list[k], list[i]);
 	}
 }
//汉诺塔
//把a塔座上的n个圆盘，借助c，移动到b(移动过程中，圆盘必须始终在塔座上是从上到下从小到大）
void hanoi (int n, int a, int b, int c){
{
	if(n > 0){
		hanoi(n-1, a, c, b);
		move(a, b);
		hanoi(n-1, c, b, a);
	}
}
//整数划分问题
//将正整数n表示成一系列正整数之和
//将最大加数n1不大于m的划分个数记作q(n,m)，可建立递推关系
//q(n,1)=1, n≥1，当最大加数n1不大于1时，任何正整数n只有一种划分形式即n个1，{1,1,1,...,1}
//q(n, m)=q(n, n), m≥n，最大加数n1实际上不能大于n。因此，q(1, m)=1。
// q(n, n)=1+q(n, n-1)，正整数n的划分由n1 =n的划分和n1≤ n-1的划分组成。
//q(n, m)=q(n-m, m)+q(n, m-1), n>m>1，正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1 的划分组成
/* 当n > m > 1时，n的所有最大加数不超过m的划分可以分为互斥且完备的两类：
1. 划分中包含m的情况
这类划分的特点是至少有一个加数等于m。由于划分中的加数是非递增排列的，这意味着第一个加数就是m。
数学表达：{m, {x₁, x₂, ..., xᵢ}}，其中x₁ + x₂ + ... + xᵢ = n - m，且x₁ ≤ m（因为加数是非递增的） 
划分个数：这类划分的个数等于q(n-m, m)。这是因为：
我们已经确定划分中包含一个m，剩下的总和是n-m
对剩下的n-m进行划分时，最大加数仍然可以不超过m（因为可以有多个m）
因此这相当于求n-m的最大加数不超过m的划分数 
示例：对于q(6,3)中包含3的划分：
3+3（对应q(6-3,3)=q(3,3)）
3+2+1（对应q(3,3)中的2+1）
3+1+1+1（对应q(3,3)中的1+1+1）
1. 划分中不包含m的情况
这类划分的特点是所有加数都小于m，即最大加数不超过m-1。
数学表达：划分中的所有加数x都满足x ≤ m-1 
划分个数：这类划分的个数等于q(n, m-1)。这是因为：
我们直接限制最大加数不超过m-1
这正好是q(n,m-1)的定义 
示例：对于q(6,3)中不包含3的划分：
2+2+2（来自q(6,2)）
2+2+1+1（来自q(6,2)）
2+1+1+1+1（来自q(6,2)）
1+1+1+1+1+1（来自q(6,2)） */
int q(int n, int m){
 	if ((n<1)||(m<1))  return 0;
 	if ((n==1)||(m==1)) return 1;
 	if (n<m) return q(n, n);
 	if (n==m) return q(n, m-1)+1;
 return q(n, m-1)+q(n-m, m);
}

递归算法复杂度的计算

递推方程求解

1. 迭代法，数学归纳法证明

2. 换元迭代法

• 将对n的递推式换成对其他变元k的递推式
• 对k直接迭代
• 将解(关于k的函数)转换成关于n的函数

1. 递归树法
   递归树的概念

• 递归树是迭代计算的模型（迭代的图形表示）
• 递归树的生成过程与迭代过程一致
• 树上所有项恰好是迭代之后产生和式中的项
• 对递归树上的项求和就是迭代后方程的解

1. 主定理
   关键思想在于比较f(n)和$n^{log_b a}$的大小,谁大谁占主导

分治法

基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归解这些子问题，再将子问题合并得到原问题的解。

分治法使用条件的问题4个特征

• 小规模可行性
• 最优子结构（原问题能够分解为若干个规模较小的子问题）
• 合并 （能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。）
• 相互独立（和最优子结构的独立性不同，这里是指子问题之间不包含公共子问题）（该特征涉及到分治法效率，如果各子问题不独立，则分治法要做许多不必要的工作，重复地解公共子问题，此时虽也可用分治法，但一般用动态规划较好。）

分治法一般算法设计模式

divide_and_conquer(P){
	//如果问题P的规模不超过n0，adhoc(P)是该问题的基本子算法，可以直接求解
    if(|P|<=n0)
		adhoc(P);
	//如果问题规模超过n0，则分解为k个子问题P1,P2,...,Pk	
	divide P into smaller subinstances P1,P2,...,Pk;
	//递归求解子问题
	for(int i=1;i<=k;i++){
		yi=divide_and_conquer(Pi);
	}
	//merge()是合并子算法，将P的子问题P1，P2...的解y1,y2...合并为原问题P的解
	return merge(y1,y2,...,yk);
}

分治法的复杂度分析

假定

• 分成k个规模为n/m的子问题去解。
• 分解为k个子问题和将k个子问题的解合并需用f(n)个单位时间。
• 解规模为1的问题耗费1个单位时间。
• 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间

常见基础分治算法

1. 二分搜索
   给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x。

   int BinarySearch(int a[],int target,int size){
   	int left=0;int right=size-1;
   	int mid;
   	while(left<=right){
   		mid=left+(right-left)/2;
   		if(a[mid]==target){return mid;}
   		if(a[mid]<target){
   			left=mid+1;
   		}else{
   			right=mid-1;
   		}
   	}
   	return -1;
   }
   //复杂度分析
   /* 每执行一次算法中的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(log2n)次。循环体内运算需要O(1)时间，因此整个算最坏情况下的计算时间复杂性为O(log2n) 。 */

2. 大整数的乘法
   思想：减少乘法的次数

3. Strassen矩阵乘法
   思想：减少乘法次数，分块矩阵

4. 二分归并排序
   归并排序按照元素在序列中的位置对序列进行划分

   void MergeSort(int a[],int left,int right){
   	if(left<right){
   		int i=(left+right)/2;
   		MergeSort(a,left,i);
   		MergeSort(a,i+1,right);
   		Merge(a,b,left,i,right);//将两个排好序的数组段合并到一个新数组b中
   		copy(a,b,left,right)；//将合并后的b复制到a中
   	}
   }

5. 快速排序
   快速排序按照元素的值对序列进行划分。
   以第一个元素/记录作为轴值，对待排序序列进行划分
   的过程为：

   1. 初始化：取第一个记录作为基准，设置两个参数i，j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置，也就是本次划分的区间；
   2. 右侧扫描过程：将基准记录与j指向的记录进行比较，如果j指向记录的关键码大，则j前移一个记录位置。重复右侧扫描过程，直到右侧的记录小（即反序）。若i＜j，则将基准记录与j指向的记录进行交换；
   3. 左侧扫描过程：将基准记录与i指向的记录进行比较，如果i指向记录的关键码小，则i后移一个记录位置。重复左侧扫描过程，直到左侧的记录大（即反序）。若i＜j，则将基准记录与i指向的记录交换；
   4. 重复2、3步，直到i与j指向同一位置，即基准记录最终的位置

      //一次划分算法伪代码
      int Partition(int r[],int first,int end){
      	i=first;j=end;
      	while(i<j){
      		while(i<j&&r[i]<=r[j]) j--;
      		if(i<j){
      			swap(r[i],r[j]);
      			i++
      		}
      		while(i<j&&r[i]<=r[j]) i++;
      		if(i<j){
      			swap(r[i],r[j]);
      			j--
      		}
      	}
      	return i;
      }
      void QuickSort(int r[],int first,int end){
      	if(first<end){
      		int pivot=Partition(r,first,end);
      		QuickSort(r,first,pivot-1);
      		QuickSort(r,pivot+1,end);
      		}
      	}
      }

6. 最近点对问题

7. 棋盘覆盖问题

   void ChessBroad(int tr,int tc,int dr,int dc,int size){
   	//tr,tc为左上角坐标，dr,dc为特殊方格坐标，size为棋盘大小
   	if(size==1) return ;
   	int t=tile++;//L型骨牌号
   	s=size/2;//分割棋盘
   	//覆盖左上角子棋盘
   	if(dr<tr+s&&dc<tc+s)//特殊方格在左上角子盘
   		ChessBroad(tr,tc,dr,dc,s);
   	else{
   		//不在左上角子盘
   		Broad[tr+s-1][tc+s-1]=t;//用t号L型骨牌覆盖右下角
   		ChessBroad(tr,tc,tr+s-1,tc+s-1,s);//覆盖其余方格
   	}
   	//覆盖右上角子棋盘
   	if(dr<tr+s&&dc>=tc+s)//特殊方格在右上角子盘
   		ChessBroad(tr,tr+s,dr,dc,s);
   	else{
   		//不在右上角子盘
   		Broad[tr+s-1][tc+s]=t;//用t号L型骨牌覆盖左下角
   		ChessBroad(tr,tc+s,tr+s-1,tc+s,s);//覆盖其余方格
   	}
   	//覆盖左下角子棋盘
   	if(dr>=tr+s&&dc<tc+s)//特殊方格在左下角子盘
   		ChessBroad(tr+s,tc,tr+s,dc,s);
   	else{
   		//不在左下角
   		Broad[tr+s][tc+s-1]=t;//用t号L型骨牌覆盖右上角
   		ChessBroad(tr+s,tc,tr+s,tc+s-1,s);
   	}
   	//覆盖右下角子棋盘
   	if(dr>=tr+s&&dc>=tc+s)
   		ChessBroad(tr+s,tc+s,tr+s,dc,s);
   	else{
   		Broad[tr+s][tc+s]=t;//用t号L型骨牌覆盖左上角
   		ChessBroad(tr+s,tc+s,tr+s,tc+s,s);
   	}
   }

动态规划

基本思想

基本思想：和分治算法类似，都是把原问题分解为规模较小的子问题，子问题都可解（最优子结构）。与分治不同的是，子问题在求解过程中是不独立的，如果不进行优化，很多子问题将被重复计算。
如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。（动态规划就是用一个表来记录所有已解决的子问题）

基本步骤

1. 分析最优解的结构：判断是否具有最优子结构，能否用DP
2. 定义递推公式（状态转移方程）
3. 自底向上递推计算子问题的最优值
4. 根据第三步记录的最优值信息，构造最优解

最优子结构

最优性原理(Optimal Principle)：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。
如果一个问题满足最优性原理/优化原则通常称此问题具有最优子结构性质。

最优子结构的性质可以用一句话概括：一个大问题的最优解，可以通过其小问题的最优解组合得到。
举个例子来理解：
最短路径问题：
比如从A到C的最短路径经过B，那么这条路径一定包含A到B的最短路径和B到C的最短路径。如果其中一段不是最短的，那整体路径也不是最短的
拼积木：
假设你要用积木搭一个最高的塔，那么整个塔的最高高度一定由每一层“当前能搭的最高积木”决定。如果某一层没选最高的积木，整体塔的高度就不是最优的

关键点：
局部最优决定全局最优：子问题的最优解能“拼出”原问题的最优解。
独立性：子问题之间不能互相干扰（比如最短路径中，A→B和B→C的路径选择互不影响）

反例（没有最优子结构的情况）：
最长简单路径：从A到B再到C的最长路径，不一定由A→B和B→C的最长路径组成，因为可能重复经过某些点
简单说，最优子结构就是“整体最优靠局部最优”，这是动态规划和贪心算法能高效解决问题的关键

用动态规划法求解的问题具有特征：

• 能够分解为相互重叠的若干子问题；
• 满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。
• 用反证法分析问题是否满足最优性原理：
• 先假设由问题的最优解导出的子问题的解不是最优的；
• 然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。

动态规划时间复杂度：

备忘录各项计算量之和╋追踪解工作量
追踪解的工作量通常是问题规模的多项式函
数，一般不会超过计算的工作量

常见动态规划算法

1. 矩阵连乘问题
   考虑矩阵的连乘积A1×A2×…×An，其中Ai是矩阵，矩阵乘法满足结合律，A1×A2×…×An可以有许多不同的计算次序，不同的计算次序需要做不同的乘法运算，乘法运算的次数也不同。
   矩阵A：i行j列，B：j行k列
   AB：i行k列的矩阵，计算每个元素需要作j次乘法，总计乘法次数为：ik×j=ijk
   问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai为Pi-1×Pi阶矩阵，i=1，2…，n。试确定计算矩阵连乘积的计算次序，使得矩阵链相乘需要的总次数最少。
   输入：向量P=，其中P0, P1,…,Pn为n个矩阵的行数与列数。
   输出：矩阵链乘法次数最少的加括号位置

• 分段：子问题划分
  将矩阵连乘积简记为A[i:j] ，这里i≤j
  输入向量：
  其最好划分的运算次数：m[i, j]
• 分析：最优子结构
  计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的

• 递推公式
  i=j时，m[i,j]=0
  i<j时，m[i,j]=min{m[i,k]+m[k+1,j]+pi-1pkpj}，k=i,i+1,…,j-1

• 计算最优值
  自底向上进行求解，保存已经解决的子问题的答案

  //迭代实现
  void MatrixChain(int *p,int n,int **m,int **s){
  	//数组p存储输入参数，n为矩阵个数，m为最优值表，s为记录最优断开位置的数组
  	for(int i=1;i<n;i++){
  		m[i][i]=0;
  	}
  	//r为矩阵链长度，自底向上求解，从两个矩阵连乘开始递增
  	for(int r=2;r<=n;r++){
  		for(int i=1;i<=n-r+1;i++){
  			int j=i+r-1;
  			//为 m[i][j] 赋一个初始值，假设第一个切分点就是 i。这里的 m[i][i] 和 m[i + 1][j] 都是已经计算过的子问题的最优解。
  			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
  			s[i][j]=i;
  			//遍历可能的断开位置k,寻找最优切分点
  			for(int k=i+1;k<j;k++){
  				int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
  				if(t<m[i][j]){
  					m[i][j]=t;//更新最优值
  					s[i][j]=k;//记录断开位置
  				}
  			}
  		}
  	}
  }

• 构造最优解

  //要输出A[1:n]的最优计算次序，只需要调用Traceback(1,n,s)
  void Traceback(int i,int j,int **s){
  	if(i==j) return ;//递归调用直到s[i][j]==0
  	Traceback(i,s[i][j],s);
  	Traceback(s[i][j]+1,j,s);
  	cout<<"Multiply A"<<i<<","<<s[i][j]<<endl;
  	cout<<"and A"<<s[i][j]+1<<","<<j<<endl;
  }
  //可能的输出样例为
  /* Multiply A1,2
  and A3,6
  Multiply A1,2
  and A2,3
  Multiply A4,5
  and A5,6
  Multiply A1,3
  and A4,6 */

1. 最长公共子序列

子问题间的依赖关系
假设两个序列X=和Y=，Z=是X和Y的一个公共子序列，
若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的一个公共子序列；
若xm≠yn，zk≠xm，则Z是Xm-1和Y的一个公共子序列；
若xm≠yn，zk≠yn，则Z是X和Yn-1的一个公共子序列。
可以得到递推方程，令C[i,j]表示Xi和Yj的最长公共子序列的长度，则
C[i,j]=0，当i=0或j=0
C[i,j]=C[i-1,j-1]+1，当i,j>0且xi=yj
C[i,j]=max{C[i-1,j],C[i,j-1]}，当i,j>0且xi≠yj

伪代码

for(i=1;i<=m;i++) C[i,0]=0;
for(j=1;j<=n;j++) C[0,j]=0;
for(i=1;i<=m;i++){
	for(j=1;j<=n;j++){
	    if(x[i]==y[i]) C[i,j]=C[i-1,j-1]+1;
		else if(C[i-1,j]>=C[i,j-1]) C[i,j]=C[i-1,j];
		else C[i,j]=C[i,j-1];
	}
}

1. 背包问题

F0(y)=0，当y=0 Fk(0)=0，当k>0且y=0
F1(y)=[y/w1]v1
递推关系Fk(y)=max{Fk-1(y),Fk-1(y-wk)+vk}

dp[i][j]前i个物品放入容量为j的背包的最大价值
dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}

//二维数组
for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(w[i]<=j)//可以装第i个 
				dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+c[i]);
		}
	}
	cout<<dp[n][m]<<endl;
//一维滚动数组
for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			if(j>=w[i])//可以装第i个 
			{
				dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			}
		}
	}
	cout<<dp[m]<<endl;

1. 走方格问题
   给定一个矩形，有n*m个方格组成。起点为最
   左上角的(1,1)，假设一扫地机器人每步要么只
   能往下走1格，要么只能往右走1格。请用动态
   规划求解，当机器人走到最右下角(n,m)时，共
   有多少种走法？
   递推关系：f(i,j)=f(i-1,j)+f(i,j-1)

   int f(int n,int m){
   	f[1][1]=1;
   	for(int i=1;i<=n;i++){
   		for(int j=1;j<=m;j++){
   			if(i!=1||j!=1) f[i][j]=f[i-1][j]+f[i][j-1];
   		}
   	}
   	cout<<f[n][m]<<endl;
   }

贪心算法

贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心法求解的问题的特征

• 最优子结构性质
  当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理/优化原则。
• 贪心选择性质
  所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。

贪心算法正确性的证明

• 第一数学归纳法：适合证明涉及自然数的命题P(n)
  归纳基础：证明P(1)为真（或P(0)为真）
  归纳步骤：若对所有n有P(n)为真，证明P(n+1)为真

• 第二数学归纳法：适合证明涉及自然数的命题P(n)
  归纳基础：证明P(1)为真（或P(0)为真）
  归纳步骤：若对所有小于n的k有P(k)为真，证明P(n)为真

证明步骤：

1. 叙述一个有关自然数n的命题，该命题断定该贪心策略的执行最终将导致最优解。其中自然数n可以代表步数或问题规模

2. 证明命题对所有的自然数为真
   归纳基础（从最小实例规模开始）
   归纳步骤（第一或第二数学归纳法）

   常见贪心算法

3. 一般背包问题
   每次从物品集合中选择性价比最高的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量

4. 活动选择问题

活动选择问题：给定n个活动的集合E={1,2,…,n}，其中每个活动i都有一个开始时间si和结束时间fi，且si

1 2 3 4 5 6 7 8 9 10 11

//按照结束时间排序，然后遍历活动，选择结束时间最早且与之前活动不冲突的活动 void greedy_select(vector<Activity> A){ sort(A.begin(),A.end(),cmp); int j=0; for(int i=1;i<A.size();i++){ if(A[i].start>=A[j].end){ j=i; cout<<A[i].id<<endl; } } }

1. 哈夫曼编码

2. 最小生成树

   • Prim算法：从顶点出发，每次选择离生成树最近的顶点，直到所有顶点都包含在生成树中
   • Kruskal算法：将所有边按照权值排序，然后依次选择权值最小的边，如果该边连接的两个顶点不在同一个连通分量中，则将该边加入生成树，直到所有顶点都包含在生成树中

3. 单源最短路径问题
   Dijkstra算法：每次选择离源点最近的顶点，直到所有顶点都包含在生成树中
   x∈S⇔x∈V且从s到x的最短路径已经找到
   初始：S={s}，S=V时算法结束
   从s到u相对于S的最短路径：从s到u且仅经
   过S中顶点的最短路径
   dist[u]：从s到u相对S的最短路径的长度
   short[u]：从s到u的最短路径的长度
   dist[u]≥short[u]