第一问要求最长公共子序列,直接套模板就好了.
第二问要求数量,ans[i][j]表示第一个字符串前i个字符,第二个字符串前j个字符的最长公共子序列的数量
如果f[i][j]是由f[i-1][j]转移过来的,那么ans[i][j] += ans[i-1][j].
如果是从f[i][j-1]或f[i-1][j-1]转移过来的,同上(数组下标变化).
如果f[i][j] == f[i-1][j-1],那么说明f[i-1][j]和f[i][j-1]是从f[i-1][ij-1]转移过来的,那么ans[i][j]就把ans[i-1][j-1]加了两遍,要减去一遍.
还有就是题目中两个字符串的长度都不超过5000,如果直接暴力,会MLE.
那么,这个时候,我们的滚动数组就派上用场了.
最后说明一点,ans的初始值怎么附: 我是设第一次的i为0,那么ans[0][0] = 1,因为长度为1的A和长度为0的B的最长公共子序列有1个.
ans[1][所有] = 1;因为长度为0的A和任意长度的B最长公共子序列的个数都是1.
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 const int mod = 100000000; 7 string l,l1; 8 int f[2][5003],ans[2][5003],m; 9 10 inline int max(int a,int b) { 11 if(a >= b) return a; 12 return b; 13 } 14 15 int main() { 16 cin >> l >> l1; 17 for(int i = 0;i <= l1.length() - 1; i++) 18 ans[1][i] = 1; 19 ans[0][0] = 1; 20 for(int i = 1;i <= l.length() - 1; i++) { 21 for(int j = 1;j <= l1.length() - 1; j++) { 22 f[m][j] = max(f[m][j-1],max(f[m^1][j],f[m^1][j-1] + (l[i-1] == l1[j-1]))); 23 ans[m][j] = 0; 24 if(f[m][j] == f[m^1][j]) ans[m][j] += ans[m^1][j]; 25 if(f[m][j] == f[m][j-1]) ans[m][j] += ans[m][j-1]; 26 if(f[m][j] == f[m^1][j-1] + 1 && l[i-1] == l1[j-1]) ans[m][j] += ans[m^1][j-1]; 27 if(f[m][j] == f[m^1][j-1]) ans[m][j] -= ans[m^1][j-1]; 28 ans[m][j] = ans[m][j] % mod; 29 } 30 m = m ^ 1; 31 } 32 printf("%d\n%d",f[m^1][l1.length()-1],ans[m^1][l1.length()-1]); 33 return 0; 34 }
原文：https://www.cnblogs.com/lipeiyi520/p/12319424.html