[算法导论]#2 动态规划

引言

动态规划与分治方法类似，都是通过组合子问题的解来求解原问题．需要注意的是，动态规划(dynamic programming)这里的programming并不是指编写计算机程序，而是指一种表格法．

分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解．

动态规划也是通过组合子问题的解来求解原问题，但是与分治方法不同的是，动态规划应用于子问题重叠的情况．换句话说，就是不同的问题具有公共的子问题，这种情况下，分治方***做许多不必要的工作，它会反复地求解那些公共子问题．而动态规划对每个子问题只求解一次，将其解保存在表格中，从而避免了不必要的工作．

ACM时期最害怕的就是这类题，但是想到状态转移方程就不难，代码量也短．

现在从原理上从零开始．

最长公共子序列

最长公共子序列简称LCS

注意子序列是不连续的．像下面这个例子，设X与Y的最长公共子序列为LCS(X,Y)．

通过肉眼观察，我们可以发现子序列有如：Ａ,AB,BCB等，其中最长的是BDAB,BCAB,BCBA，长度为\(4\)

通过分析，如果用暴力枚举的方法，思路就是X有的子序列Y也有．

总的来说就是枚举X的所有子序列，然后在Y中check

来分析一下这个复杂度:

• check()复杂度为\(O(n)\)
• 枚举子序列:复杂度为\(O(2^m)\)

总复杂度是指数级别的，所以这个算法是龟速的．

现在必须设计一个更给力的算法

做一个简化:

• 优化求LCS(X,Y)的长度的算法
• 扩展这个算法最终求出LCS

为了方便，定义\(|s|\)为字符串\(s\)的长度

如果只是求长度，就不需要考虑所有的子序列，只用考虑他们的前缀．

定义\(c[i,j]=|lcs(x[1..i],y[1...j])|\)，那么\(c[m,n]\)就是最终答案

初始化\(c[0,0]=0​\)

|lcs(X,Y)| 的状态转移方程是:

我们来感性证明一下:

令\(z[1...k]=lcs(x[1...i],y[1...j])\)当\(c[i,j]=k\)的时候

同时若\(z[k]\)的取值也为\(x[i]\)，等于\(y[j]\)，那就是说\(z[1...k-1]=lcs(x[1...i-1],y[1...j-1])\)，而\(c[i-1,j-1]=k-1\)

反证法假设存在\(c[i-1,j-1]>k-1\)，因为\(x[i]=y[j]\)，所以\(c[i,j]=c[i-1,j-1]+1\)，意味着\(c[i,j]>k\)，与原命题矛盾，假设不成立．得证

其他情况也差不多．

比如假设\(z[k]=x[i]\neq y[j]\)，就是说\(z[1...k-1]=lcs(x[1...i-1],y[j])\)，而\(c[i-1,j]=k\)，之后证明也简单

动态规划的特征

最优子结构

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

如果\(z=lcs(x,y)\)，那么任何\(z\)的前缀都是某个\(x\)的前缀和某个\(y\)的前缀的\(lcs\)

重叠子问题

问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

对于\(lcs\)的代码而言，复杂度最大的那一定是失配的时候，要计算两个，实际上不需要重复计算，可以像填表一样先记下来．

无后效性

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。

空间优化

求出长度的过程中记录路径，最后再通过回溯法就可以得出\(lcs\)

总时间复杂度是\(O(n*m)\)，空间复杂度是\(O(n*m)​\)

但是求长度的空间复杂度可以降为\(O(min(n,m))\)

可以发现，每个元素的计算只与其左上，左边，上边这三个因素有关．

/**
 * 最长公共子序列
 * 优化了内存空间的使用
 * 观察到一件事: 每一个元素的计算,只和其在左上, 左边, 上边的三个元素相关
 * 可以考虑len(x) + 3
 * 3个变量 定义为leftAbove, left, above
 */
#include<iostream>
#include<string>
#include<memory.h>
using namespace std;
 
 
int LCS(string x, string y);
 
int main() {
	string x, y;
	cin>>x>>y;
	LCS(x, y);
}
 
int LCS(string x, string y){
	int lenx = x.length();
	int leny = y.length();
	
	int leftabove, left, above; //左上角 左 上
 
	int *compute = new int[leny + 1]; //compute[0] 即原来的calc[i][0] for i in [0, lenx];
	memset(compute, 0, (leny + 1) * sizeof(int));
	for(int i = 1; i <= lenx; i++) {
		leftabove = left = compute[0];
		above = compute[1];
		for(int t = 0; t <= leny; t++) cout<<compute[t]<<" ";
		cout<<endl;
		for(int j = 1; j <= leny; j++) { 
			//计算,并且更新这三个变量
			if(x[i - 1] == y[j - 1]) compute[j] = leftabove + 1;
			else if(left > above) 	compute[j] = left;
			el***pute[j] = above;
 
			//更新此三个变量,很有技巧的哦
			leftabove = above;
			above = compute[j + 1];
			left = compute[j];
		}
	}
	cout<<compute[leny]<<endl; 
	delete[] compute;
}
————————————————
版权声明：本文为CSDN博主「TomMengdle」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/TomMengdle/article/details/6946309

但是如果空间复杂度为\(O(min(n,m))​\)，那还能得出路径吗?