一道不怎么简单的dp题
我们定义状态f[i][j][k][val](其中val∈{0,1})表示A串的前i个字符,分成k段,与B串的前j个字符匹配,并且A[i]选/不选的方案数。
那么我们考虑状态的转移,
当a[i]==b[j]时,f[i][j][k][1]可以从f[i-1][j-1][k-1][0],f[i-1][j-1][k][1],f[i-1][j-1][k-1][1]三个状态转移而来;f[i][j][k][0]可以从f[i-1][j][k][1],f[i-1][j][k][0]两个状态转移而来。
当a[i]!=b[j]时,f[i][j][k][1]=0,f[i][j][k][0]可以从f[i-1][j][k][1],f[i-1][j][k][0]转移而来
由于阶段i由且仅由i-1阶段转移而来,所以我们采用滚动数组优化空间,仅存i和i-1两个阶段即可。