LeetCode115 不同的子序列
\(dp[i][j]\) 表示字符串 \(s[:i]\) 中包子序列 \(t[:j]\) 的数量
对于当前字符 \(s[i]\) 与 \(t[j]\):
注意任意字符串 \(s[:i]\) 均包含一个空串,即 \(dp[i][0] = 1\)
class Solution(object): def numDistinct(self, s, t): """ :type s: str :type t: str :rtype: int """ m, n = len(s), len(t) dp = [[0 for i in range(n + 1)] for j in range(m + 1)] for i in range(m + 1): dp[i][0] = 1 for i in range(1, m + 1): for j in range(1, n + 1): if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] return dp[m][n]