学步园

DP方式求解：

#include <iostream>
using namespace std;

/**
* 问题描述：两个字符串，求解他们的最长公共子序列，子序列不要求连续
* 
*	分析这个问题，我们可以发现有子结构，可以将X，Y两个字符串的最长公共子串
*	的问题转换成更小的子问题。而且这个问题的求解过程有重叠子问题。根据这两个
*	性质我们确定尝试用DP来解决。
*	首先定义状态，f(m,n),代表字符串X以Xm结尾的子串与字符串Y以Yn结尾的子串的
*	最长公共子序列。
*	如果Xm == Yn，那么问题转换成求解f(m-1,n-1)，且f(m,n) = f(m-1,n-1)+1
*	如果Xm != Yn，那么最长公共子序列要么是X(m-1)结尾的子串与Yn结尾的子串的最长公共子序列
*								    要么是Xm结尾的子串与Y(n-1)结尾的子串的最长公共子序列
*	根据上面分析很容易写出状态转移方程(递推式)：
*	f(m,n) = 
*		f(m,n) = f(m-1,n-1)+1.				Xm == Yn
*		f(m,n) = max{f(m,n-1),f(m-1,n)}.	Xm != Yn
*
*   下面代码的任务就是自底向上求解这个状态转移方程。
*/
#define M 8	//行
#define N 7	//列
int dp[M][N] = {0};

int lcs_max(int x, int y){
	return x>y?x:y;
}

/**
* DP求解最长公共子序列
*/
int lcs(const char *a, const char *b){	
	int row = M;
	int col = N;

	//初始化第一行和第一列
	if(a[0] == b[0]) dp[0][0] = 1;
	else dp[0][0] = 0;
	for(int i=1;i<N;i++){
		if(a[0] == b[i]) dp[0][i] = 1;
		else dp[0][i] = 0;
	}
	for(int j=1;j<M;j++){
		if(b[0] == a[j]) dp[j][0] = 1;
		else dp[j][0] = 0;
	}

	//核心代码：自底向上求解DP矩阵(注意a是列，b是行)
	for(i=1;i<row;i++){
		for(j=1;j<col;j++){
			if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;
			else dp[i][j] = lcs_max(dp[i-1][j], dp[i][j-1]);
		}
	}

	//输出lcs矩阵
	for(i=0;i<row;i++){
		for(j=0;j<col;j++){
			cout<<dp[i][j];
		}
		cout<<endl;
	}

	//返回最长子序列值
	return dp[row-1][col-1];
}

int main(){
	char *a = "aceddbcs";	//a作为DP矩阵的列(故DP矩阵8行)
	char *b = "cebsdbc";	//b作为DP矩阵的行(故DP矩阵7列)
	cout<<lcs(a,b)<<endl;
	return 0;
}