Distinct Subsequence

It's a typical string matching 2D dynamic programming question. For 2 strings, we construct 2 table to calculate the result for each length.

Code in Python:

class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        slen = len(s)
        tlen = len(t)
        dp = [[0 for _ in xrange(tlen+1)] for _ in xrange(slen+1)] 
        for i in xrange(slen+1):
            dp[i][0] = 1
        for i in xrange(1, slen+1):
            for j in xrange(1, tlen+1):
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(s[i-1]==t[j-1])
        return dp[-1][-1]

The substructure dp[i][j] = dp[i-1][j] + dp[i-1][j-1]*(s[i-1]==t[j-1]) means that when we get a new character from s, its value depends on the result when this character wasn't there. Besides, if the character match the character from t, we can see the result when both letters weren't there and decide whether we can increment our answer.