题目求两个字符串s1,s2不同的LCS个数。
经典的求LCS的DP是这样的：
- LCS[i][j]表示s1[0...i]和s2[0...j]的LCS
- LCS[i][j]从LCS[i-1][j-1]+1（s1[i]==s2[j]）或max(LCS[i-1][j],LCS[i][j-1])（s1[i]!=s2[j]）转移来
计数的话也跟着转移，用dp[i][j]计数。不过搞不出。。看了别人的解法才恍然大悟，要减去多算的部分，即s1[i]!=s2[j]且LCS[i-1][j]等于LCS[i][j-1]时这种情况的转移，如果只是dp[i][j]=dp[i-1][j]+dp[i][j-1]可能会有重复算的部分：
- LCS[i-1][j]等于LCS[i][j-1]，且LCS[i-1][j-1]不与它们相等，那样s1[0...i-1]和s2[0...j]所有的LCS必定以s2[j]为结尾，s1[0...i]和s2[0...j-1]同理，所以s1[0...i-1]和s2[0...j]所有的LCS和s1[0...i]和s2[0...j-1]的所有LCS没有相交部分，dp[i][j]=dp[i-1][j]+dp[i][j-1]；
- 而如果LCS[i-1][j-1]等于它们的情况，就说明存在不以s1[i]和s2[j]结尾的LCS，多算了一次s1[0...i-1]和s2[0...j-1]的所有LCS的部分，这时dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]。
另外注意负数取模。
#include<cstdio>
#include<cstring>
using namespace std;
int lcs[][],d[][];
int main(){
char s1[],s2[];
int t;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%s%s",s1+,s2+);
int l1=strlen(s1+),l2=strlen(s2+);
for(int i=; i<=l1; ++i) d[i][]=;
for(int i=; i<=l2; ++i) d[][i]=;
for(int i=; i<=l1; ++i){
for(int j=; j<=l2; ++j){
if(s1[i]==s2[j]){
lcs[i][j]=lcs[i-][j-]+;
d[i][j]=d[i-][j-];
}else if(lcs[i-][j]==lcs[i][j-]){
lcs[i][j]=lcs[i-][j];
d[i][j]=(d[i-][j]+d[i][j-])%;
if(lcs[i-][j-]==lcs[i-][j]) d[i][j]=((d[i][j]-d[i-][j-])%+)%;
}else if(lcs[i-][j]>lcs[i][j-]){
lcs[i][j]=lcs[i-][j];
d[i][j]=d[i-][j];
}else{
lcs[i][j]=lcs[i][j-];
d[i][j]=d[i][j-];
}
}
}
printf("Case %d: %d\n",cse,d[l1][l2]);
}
return ;
}