字符串如何求给定子序列的数量（动态规划求解） 模板_求子序列的个数

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

假设 S=”rabbbit“ ，T=”rabbit“

下面是图例

• 最终结果是dp[T.size()][S.size()]
• 每当T[i] == S[j]时， dp[i][j]会增加， 比如S = rabb, T = rab. 此时dp[i][j] = dp[i][j-1] + x （x为增加量）
• 当T[i] != S[j]时 dp[i][j] 会不变
• x是什么呢?，对于例子S=rabbb， T=rabb, x为2， 而dp[i-1][j-1] = 2, 而且其他的例子也能推出来，所以可以假设x = dp[i-1][j-1]
• 当计算dp[i][j]时， dp[i][j-1]是一定被包括进去的， 当两个字符串的最后一个字