问题115：给定一个字符串S和一个字符串T，计算在S的子序列中T出现的次数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是.
来源：力扣（LeetCode）
链接：https://leetcode.com/problems/distinct-subsequences
这道题很明显要用动态规划方法，DP[i][j]表示S的前j个字符组成的子序列中，T的前i个字符出现的次数。
初始条件：
- 当
T为空，S为空时，有一个解：DP[0][0] = 1； - 当
T为空，S不为空时，有一个解：DP[0][j] = 1, j > 0； - 当
S为空，T不为空时，无解：DP[i][0] = 0, i > 0。
状态转移方程：
- 当
s[j] != t[i]时，也就是说，s[j]不能做出任何贡献，因此DP[i][j] = DP[i][j-1]； - 当
s[j] == t[i]时，s[j]可以用来抵消t[i]，当然也可以不使用s[j]。因此DP[i][j] = DP[i-1][j-1] + DP[i][j-1]；
完整代码：
class Solution:
def numDistinct(self, s: str, t: str) -> int:
matrix = [[0 for _ in range(len(s)+1)] for _ in range(len(t)+1)]
for j in range(len(s)+1):
matrix[0][j] = 1
for i in range(1, len(t)+1):
for j in range(1, len(s)+1):
if t[i-1] == s[j-1]:
matrix[i][j] = matrix[i-1][j-1] + matrix[i][j-1]
else:
matrix[i][j] = matrix[i][j-1]
return matrix[len(t)][len(s)]
运行结果：
image.png
