最长公共子序列求方案数

题目链接

参考

在最长公共子序列问题中，状态的划分有两类：

1. a[i]==b[j]
   f[i][j]=f[i-1][j-1]+1;
2. a[i]!=b[j]
   f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1])

不过，考虑到f[i-1][j-1]可以通过f[i-1][j]或f[i][j-1]转移而来，我们通常将a[i]!=b[j]时的转移方程写为 f[i][j]=max(f[i-1][j],f[i][j-1]）
可以发现，但在这种划分方式中，我们仅仅做到了不漏，而没有做到不重，因为f[i-1][j]和f[i][j-1]都包含了f[i-1][j-1]
因此在求方案数时，就有了一个大坑