题意：给2个字符串求其最大公共子序列的长度。
解法：这个和一般的状态定义有点不一样，f[i][j]表示 str 前i位和 str2 前j的最大公共子序列的长度，而不是选 str 的第i位和 str2 的第j位。
仔细想想就可以知道只表示“前...”的状态可以保证每次拓展答案时，之前的状态已经保证了“公共”，因此str[i]==str2[j]时f[][]+1也不会错。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int L=210; 8 int f[L][L]; 9 char str[L],str2[L]; 10 11 int mmax(int x,int y) {return x>y?x:y;} 12 int main() 13 { 14 while (scanf("%s%s",str+1,str2+1)!=EOF) 15 { 16 int len=strlen(str+1),len2=strlen(str2+1); 17 f[0][0]=0; 18 for (int i=1;i<=len;i++) 19 for (int j=1;j<=len2;j++) 20 { 21 f[i][j]=mmax(f[i-1][j],f[i][j-1]); 22 if (str[i]==str2[j]) f[i][j]=mmax(f[i][j],f[i-1][j-1]+1); 23 } 24 printf("%d\n",f[len][len2]); 25 } 26 return 0; 27 }
原文：http://www.cnblogs.com/konjak/p/5906328.html