distinct_subsequences.py

class Solution: 
    # @param S, T: Two string.
    # @return: Count the number of distinct subsequences
    def numDistinct(self, S, T):
        # write your code here
        '''
        根据题目提供的例子，建一张二维表：
            r a b b b i t (S)
        r 0 1 1 1 1 1 1 1   
        a 0 0 1 1 1 1 1 1
        b 0 0 0 1 2 3 3 3
        b 0 0 0 0 1 3 3 3 ＃ 关键在第一个3
        i 0 0 0 0 0 0 3 3
        t 0 0 0 0 0 0 0 3
        (T)
        dp[i][j] = dp[i][j - 1] + (T[i - 1] == S[j - 1] ? dp[i - 1][j - 1] : 0)
        '''
        rows = len(T) + 1
        cols = len(S) + 1
        caches = [[0] * cols for i in xrange(rows)]
        caches[0] = [1] * cols
        for i in xrange(1, rows):
            for j in xrange(1, cols):
                caches[i][j] = caches[i][j - 1]
                if T[i - 1] == S[j - 1]:
                    caches[i][j] += caches[i - 1][j - 1]
        return caches[-1][-1]