給定一個(gè)字符串 s 和一個(gè)字符串 t ，計(jì)算在 s 的子序列中 t 出現(xiàn)的個(gè)數(shù)。
字符串的一個(gè) 子序列 是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對(duì)位置所組成的新字符串。（例如，"ACE" 是 "ABCDE" 的一個(gè)子序列，而 "AEC" 不是）
題目數(shù)據(jù)保證答案符合 32 位帶符號(hào)整數(shù)范圍。
輸入：s = "rabbbit", t = "rabbit"
輸出：3
解釋：
如下圖所示, 有 3 種可以從 s 中得到 "rabbit" 的方案。
(上箭頭符號(hào) ^ 表示選取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
采用DP，重點(diǎn)在于狀態(tài)轉(zhuǎn)移方程。令二維數(shù)組distinct_nums[][]，distinct_nums[i][j]表示s[0...j]的子序列中t[0...i]出現(xiàn)的個(gè)數(shù)。我們可以這樣來填充distinct_nums[][]。如果s[j]不等于t[i]，那子串不可能以s[j]結(jié)尾，故distinct_nums[i][j] = distinct_nums[i][j - 1]。如果s[j]等于t[i]，那則有兩種情況，子串以s[j]結(jié)尾(distinct_nums[i - 1][j - 1])或者不以s[j]結(jié)尾(distinct_nums[i][j - 1])?？偨Y(jié)下來：

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]

時(shí)間空間復(fù)雜度均為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]