动态规划dp———LCS 最长公共子序列

一、什么是最长公共子序列

　　例：设有两个字符串str1="nyiihaoo" , str2="niyeyiyang"，那么"nyiihaoo"中的子序列："ny" 长度是2； "niyeyiyang"中的子序列："ny"长度也为2，这是str1与str2的一个公共子序列，长度为2。那么这两个字符串最长的公共子序列应该是什么呢?  显然是        "nyi ih a oo"（或  "ny i i h a oo"） 中"nyia"   以及   "n i y ey i y a ng"（或" n iye yi y a ng "）中的"nyia"  : 其"nyia"长度是4，在str1和str2中我们找不到长度大于4的最长公共子序列了。所以str1和str2的最长公共子序列的长度是4。

二、动态规划（dynamic programing）解决最长公共子序列长度问题

　　我们首先定义一个二维数组 dp[i][j]  其含义是：str1中前 i-1 个字符 与 str2中前j-1个字符中最长公共子序列的长度。          

　　这时我们要找出其动态转移方程，分析 ( 要结合数组的意义理解 ) ：

　　　　　　当  str1[i-1]==str2[j-1]  , dp[i][j]  =  dp[i-1][ j-1]+1 ;

　　　　　　否则：d[i][j] = max{   dp[i-1][ j ]  ,dp[ i ][ j-1 ] };

三、代码实现（c++）

　　　　　

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int a[2000][2000];
int main(){
	string str1,str2;
	while(cin>>str1>>str2){
		memset(a,0,sizeof(a));
		int i=0,j=0;
		for(int i=1;i<=str1.length();i++){
			for(int j=1;j<=str2.length();j++){
				if(str1[i-1]==str2[j-1]){
					a[i][j]=a[i-1][j-1]+1; 
				}
				else{
					a[i][j]=max(a[i-1][j],a[i][j-1]);
				}	
			}
		}
		cout<<a[str1.length()][str2.length()]<<endl;
	}
}