[DP/BackTracking]115. Distinct S

• 分类：DP/BackTracking
• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)-->O(n)因为只和上一行有关所以可以存上一行的数据

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个地方：

• state: dp[i][j]代表num of subseq of s[1:j] equals t[1:i]
• init:dp[0][*]=1 当t为字符串的时候仅有1个解
• function:如果两个字符一样，那么等于两个字符之前的字符串的解加上skip掉s[j]的解，如果不一样，那么直接是skip掉s[j]的解
• ans
  4.这道题的O(n)方法也好难啊，主要还是要对着例子，逐一突破就做出来了

5. 记忆化递归是个好方法简单明了！