• 分類：DP/BackTracking
• 時(shí)間復(fù)雜度: O(n^2)
• 空間復(fù)雜度: O(n^2)-->O(n)因?yàn)橹缓蜕弦恍杏嘘P(guān)所以可以存上一行的數(shù)據(jù)

115. Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

代碼：

DP原始解法：

class Solution:
    def numDistinct(self, s: 'str', t: 'str') -> 'int':
        m=len(t)
        n=len(s)
        # init
        dp=[[0 for i in range(n+1)] for i in range(m+1)]
        dp[0]=[1 for i in range(n+1)]
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if t[i-1]==s[j-1]:
                    dp[i][j]=dp[i-1][j-1] #一種是match上了，一種是吧s[j]skip掉
                dp[i][j]+=dp[i][j-1]
                    
        return dp[-1][-1]

DPO(n)解法：

class Solution:
    def numDistinct(self, s: 'str', t: 'str') -> 'int':
        m=len(t)
        n=len(s)
        # init
        dp={0:[1 for i in range(n+1)],1:[0 for i in range(n+1)]}
        
        for i in range(1,m+1):
            for j in range(0,n+1):
                if j==0:
                    ans=0
                else:
                    if t[i-1]==s[j-1]:
                        ans+=dp[(i-1)%2][j-1]
                dp[(i)%2][j]=ans       
                    
        return dp[m%2][-1]

記憶化遞歸解法：

class Solution:
    def numDistinct(self, s: 'str', t: 'str') -> 'int':
        m=len(t)
        n=len(s)     
                    
        return self.helper(s,t,m,n,{})
    
    def helper(self,s,t,m,n,memo):
        
        if (m,n) in memo:
            return memo[(m,n)]
        
        #寫出口
        if m==0:
            return 1
        if n==0:
            return 0

        if s[n-1]==t[m-1]:
            res=self.helper(s,t,m-1,n-1,memo)+self.helper(s,t,m,n-1,memo)
        else:
            res=self.helper(s,t,m,n-1,memo)
            
        memo[(m,n)]=res
        return memo[(m,n)]

討論：

1.這道題是一道很難的DP（反正我覺得很難）
2.這道題的講解看的是公瑾講解
3.最主要的還是4個(gè)地方：

• state: dp[i][j]代表num of subseq of s[1:j] equals t[1:i]
• init:dp[0][*]=1 當(dāng)t為字符串的時(shí)候僅有1個(gè)解
• function:如果兩個(gè)字符一樣，那么等于兩個(gè)字符之前的字符串的解加上skip掉s[j]的解，如果不一樣，那么直接是skip掉s[j]的解
• ans
  4.這道題的O(n)方法也好難啊，主要還是要對著例子，逐一突破就做出來了

5. 記憶化遞歸是個(gè)好方法簡單明了！