class Solution(object):
    def numDistinct(self, s, t):
        """
        不同的子序列：https://leetcode-cn.com/problems/distinct-subsequences/

        :type s: str
        :type t: str
        :rtype: int
        """
        # 如何计算字符串S中出现T的个数？（很重要）
        # 如果S[0] == T[0]:那么等价于计算"S[1:],T[1:]的不同子序列问题" + "S[1:],T[:]的不同子序列问题"（重复性）
        # 如果S[0] != T[0]:那么等价于计算"S[1:],T[:]的不同子序列问题"（重复性）
        # 基于上述理论我们:
        # 定义状态dp[i][j]：表示S[i:]和T[j:]的不同子序列数量
        # 那么状态转移方程：
        # if S[i] == T[j]: dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
        # if S[i] != T[j]: dp[i][j] = dp[i + 1][j]
        # 可以看到上面递推关系是从后到前的，直到求解到dp[0][0],问题得解
        # 开始写代码：
        # 由于上面涉及到i+1,j+1的长度，所以dp定义为S和T字符串长度+1,这样dp才对i+1,j+1才不会越界
        dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
        # 思考：dp[:][-1],dp[-1][:]的值是什么？
        # 由于dp[i][j]：S[i:]和T[j:]的不同子序列
        # 所以当i==len(S)，dp表示S[len(S):]字符串(即"")出现T的子序列的个数，很明显值为0
        # 当 j==len(T), dp表示S字符串出现T[len(T):]字符串(即"")的子序列的个数，很明显为1
        # 当 i==len(S) and j==len(T)的时候，明显为1
        # 所以初始化：
        for i in range(len(s) + 1):
            dp[i][-1] = 1
        # 开始填充二维数组dp（时刻记住，i为s的下标，j为t的下标）
        # 从上面可以看到只有当计算出dp[i + 1][j + 1]和dp[i + 1][j]后，才能计算dp[i][j]
        # 所以我们循环要"从后往前"，而循环顺序要"先j后i"（还是迷糊直接画表格秒懂）（时刻记住，i为s的下标，j为t的下标）
        # 附上一个例子的dp最终数值直接看就明白循环顺序：
        # 输入S："rabbbit"
        # 输入T："rabbit"
        #     r  a  b  b  i  t  ""  
        #  r [3, 3, 3, 3, 1, 1, 1]  --> i = 0
        #  a [0, 3, 3, 3, 1, 1, 1]  --> i = 1
        #  b [0, 0, 3, 3, 1, 1, 1]  --> i = 2
        #  b [0, 0, 1, 2, 1, 1, 1]  --> i = 3
        #  b [0, 0, 0, 1, 1, 1, 1]  --> i = 4
        #  i [0, 0, 0, 0, 1, 1, 1]  --> i = 5
        #  t [0, 0, 0, 0, 0, 1, 1]  --> i = 6
        #  ""[0, 0, 0, 0, 0, 0, 1]  --> i = 7
        #     |  |  |  |  |  |  |
        #  j= 0  1  2  3  4  5  6
        for j in range(len(t))[::-1]:
            for i in range(len(s))[::-1]:
                if t[j] == s[i]: 
                    dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j]
                else: 
                    dp[i][j] = dp[i + 1][j]
        return dp[0][0]










