动态规划7：最长公共子序列（LCS）

递归关系如下：

#include <iostream>  
#include <string>
using namespace std;  
  
#define MAX 100
void main()   
{  
	string a="abcdef";
	string b="abcfeg";
	int lena=a.length();
	int lenb=b.length();
	int dp[MAX][MAX]={0};
	for(int i=1;i<=lena;++i){
		for(int j=1;j<=lenb;++j){
			if(i==1||j==1)dp[i][j]=0;
			else if(a[i-1]==b[j-1])
				dp[i][j]=dp[i-1][j-1]+1;
			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}

	cout<<dp[lena][lenb];
}  #include <iostrea