Distinct Subsequences

这道题的匹配思路是很类似于LCS那道题的，毕竟这算是LCS的一个衍生问题，题目的要求是要我们在S里找能凑成T的子序列的个数，这里假设当S[i]==T[j]，如果在这种情况下，dp[i][j]的值应该是dp[i - 1][j - 1]和dp[i][j - 1]的和，dp[i - 1][j - 1]相当于当前字符串相等，我们就找S没有这个两个字符时的匹配情况，如果那个情况匹配的话，那加上当前这两个字符相等加起来还是匹配的，而dp[i][j - 1]的情况是说明当没有当前S这个串的时候一样可以匹配的情况，状态方程如下

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

另外这里应该把s字符串放在横排来进行DP，下面是整个代码，空间复杂度还可以优化到O(m)，懒得做了

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        n = len(t)
        if not n:
            return 1

        m = len(s)
        if not m:
            return 0

        dp = [[0] * (m + 1) for _ in xrange(n + 1)]
        for i in xrange(m + 1):
            dp[0][i] = 1

        for i in xrange(1, n + 1):
            for j in xrange(i, m + 1):
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] if s[j - 1] == t[i - 1] else dp[i][j - 1]

        return dp[n][m]