i
i+1
....B B
D
.....A B
C
j j+1
假设dp[i][j]为以i，j结尾的最大公共子串
循环到i，j时，我们假设dp[i-1][j],dp[i-1][j-1],dp[i][j-1]都已经得出最优解
若i与j不匹配，那么dp[i][j]=max(dp[i-1][j],dp[i][j-1])
若i与j匹配，那么dp[i][j]=dp[i-1][j-1]+1，可以看出，即使i-1与j也已经匹配，i与j匹配也仍然不影响最优解的值
先贴个滚动数组的代码：
#include<iostream> #include<cstring> #include<cmath> using namespace std; char str1[500],str2[500]; int dp[2][500]; int lcs(char* str1,char* str2){//1??ˉêy×é?ú???ú′? //???ü1??ˉμúò??? memset(dp,0,sizeof(dp)); int len1=strlen(str1),len2=strlen(str2); for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) dp[i%2][j]=dp[(i-1)%2][j-1]+1; else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]); } return dp[len1%2][len2]; } int main (){ while(cin>>str1>>str2){ cout<<lcs(str1,str2)<<endl; } return 0; }
没有滚动数组的代码
//状态转移的一种方法是根据一个序列的结尾入手找出规律 #include<iostream> #include<cstring> #include<cmath> using namespace std; char str1[100],str2[100]; int dp[100][100]; int lcs(char* str1,char* str2){//O(mn)算法 memset(dp,0,sizeof(dp)); //注意str1[0]==str2[i]时，dp[0][i]不满足算法 //所以让dp的下标进一位，str1[0]==str2[i-1]时,dp[1][i]=dp[0][i-1]+1=0+1=1 int len1=strlen(str1),len2=strlen(str2); for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++) { if(str1[i-1]==str2[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } return dp[len1][len2]; } int main (){ while(cin>>str1>>str2){ cout<<lcs(str1,str2)<<endl; } return 0; }
hdu 1159 Common Subsequence O(nm)dp算法
原文：http://www.cnblogs.com/neverchanje/p/3566427.html
