7.4 - hard - 24

115. Distinct Subsequences
一道dp问题，dp的难点在于一是要找准状态，state，二是找递推公式，然后就是初始化，最后就是求结果。就是这几步，一般第一步最难，也就是找到 dp的维度和意义。

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        # dp[i][j] means ending with t[i], s[j] how many subsequence matches
        # if t[i] == s[j]: dp[i][j] = sum(dp[i-1][k]) for k in 0...j-1)
        # else: dp[i][j] = 0
        if not s or not t:
            return 0
        dp = [[0 for _ in range(len(s))] for _ in range(len(t))]
        for i in range(len(s)):
            if t[0] == s[i]:
                dp[0][i] = 1
        
        for i in range(1, len(t)):
            for j in range(len(s)):
                if s[j] == t[i]:
                    dp[i][j] = sum([dp[i-1][k] for k in range(j)])
        
        return sum(dp[-1])