115. 不同的子序列

https://leetcode-cn.com/problems/distinct-subsequences/submissions/

解法一：回溯（暴力）

虽然排除了一些不必要的情况，然而还是超时

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        self.count = 0  #全局统计
        tmp = ""
        self.backtrack(0, tmp, s, t)
        return self.count

    def backtrack(self, idx, tmp, s, t):
        #找到一个t
        if tmp == t:
            self.count += 1
        #剩余部分达不到tmp长度时，直接pass
        if len(tmp) + len(s) - idx < len(t):
            return
        else:
            #对s串的idx位置到串末，逐个试探
            for i in range(idx, len(s)):
                tmp += s[i]
                #对下一位递归
                self.backtrack(i + 1, tmp, s, t)
                tmp = tmp[:-1]

解法二：dp

思路见：https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java

简单来说就是用dp[i+1][j+1]来表示t[0...i]在s[0...j]中匹配。为何要+1？因为dp[0][j]均为1，表示空串在任何串中出现一次。dp[1...i][0]=0，表示任何串在空串中都不出现。

关键是s[0...j]和t[0...i]，当s[j]==t[i]时，子序列数有两种来源：

1.t[0...i-1]在s[0...j-1]中出现次数（加上s[j]和t[i]仍然匹配）

2.t[0...i]在s[0...j-1]中出现次数（不用看t[i]就已经匹配了）

当s[j]！=t[i]时，子序列数不变

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0 for _ in range(len(s)+1)] for _ in range(len(t)+1)]
        for j in range(len(s)+1):
            dp[0][j] = 1
        for i in range(len(t)):
            for j in range(len(s)):
                if s[j] == t[i]:
                    dp[i+1][j+1] = dp[i][j] + dp[i+1][j]
                else:
                    dp[i+1][j+1] = dp[i+1][j]

        return dp[len(t)][len(s)]