115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
采用DP，重点在于状态转移方程。令二维数组distinct_nums[][]，distinct_nums[i][j]表示s[0...j]的子序列中t[0...i]出现的个数。我们可以这样来填充distinct_nums[][]。如果s[j]不等于t[i]，那子串不可能以s[j]结尾，故distinct_nums[i][j] = distinct_nums[i][j - 1]。如果s[j]等于t[i]，那则有两种情况，子串以s[j]结尾(distinct_nums[i - 1][j - 1])或者不以s[j]结尾(distinct_nums[i][j - 1])。总结下来：

distinct_nums[i][j] = distinct_nums[i - 1][j - 1] + distinct_nums[i][j - 1] if s[j] == t[i] else distinct_nums[i][j - 1]

时间空间复杂度均为O(s * t)。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # cover the edge cases
        if t == '':
            return 1
        if s == '':
            return 0

        distinct_nums = list()
        for _ in range(len(t)):
            distinct_nums.append([0] * len(s))

        # initialise the first line
        for idx in range(len(s)):
            if s[idx] == t[0]:
                distinct_nums[0][idx] = (distinct_nums[0][idx - 1] + 1) if idx > 0 else 1
            else:
                distinct_nums[0][idx] = distinct_nums[0][idx - 1] if idx > 0 else 0

        # from left to right, top to down, fill the matrix
        for i in range(1, len(t)):
            for j in range(1, len(s)):
                distinct_nums[i][j] = distinct_nums[i][j - 1]
                if s[j] == t[i]:
                    distinct_nums[i][j] += distinct_nums[i - 1][j - 1]

        return distinct_nums[-1][-1]