115. 不同的子序列

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/distinct-subsequences/
Star
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
提示：
  • 0 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

法1 动态规划

思路
显然是双序列类型题目。按照套路如下：
  1. 定义状态：
      2. dp[i][j] ⇒ 序列s[0:i]中不同的子序列等于t[0:j]的个数
  1. 状态转移：
      • 如果s[i]==t[j]的情况。显然，这两个字符相等，我们就将注意力前移，集中在s[1:i-1]和t[1:j-1]上。dp[i-1][j-1]表示s[1:i-1]中有多少个不同的子序列等于t[1:j-1]，两边分别加上s[i]和t[j]之后，自然就有相同多数目的s[1:i]的不同子序列等于t[1:j]。所以算上这部分，dp[i][j]+=dp[i-1][j-1]。
      • 如果s[i]!=t[j]的话，说明s[i]指望不上，我们就将注意力放在s[1:i-1]上，看里面有多少个不同子序列等于t[1:j]，直接拿过来用就行，反正加上了s[i]也不管事。所以这种情况下，dp[i][j]+=dp[i-1][j].
      • 注意：当s[i]==t[j]的时候，上述的第二种情况也是要累加进去的。原因也是显然的。
      💡
      换个角度理解状态转移，如果当前s[i] == t[j], 那么我s[i]可以取也可以不取，就比如s=abb, t= b ,当s[2] == t[0] ,我s[2]可以取，也可以不取，而是让s[0:1]与t匹配. 如果取的话就是dp[i][j] = dp[i-1][j-1] ,如果不取的话就是dp[i][j] = dp[i-1][j]. 显然这两种是要加起来的。 如果s[i]≠t[j]，那么s[i]必然不能取，所以dp只能等于dp[i-1][j]
  1. 边界条件
      2. 对于dp[0][j] 显然为0 ，且如果len(t) > len(s) 可以直接返回0
      对于dp[i][0], 表示序列s中有多少个空序列，显然只有一个，直接将dp[i][0] 初始化为1即可
  1. 优化，对于j > i 的情况，肯定是为0的，所以就不用去遍历了。
题解
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if len(t) > len(s):
            return 0
        
        s = "#" + s
        t = "#" + t

        dp = [[0]*len(t) for _ in s]
        dp[0][0] = 1
        
        for i in range(1, len(dp)):
            dp[i][0] = 1
            for j in range(1, len(dp[0])):
                # j > i 时肯定没戏
                if j > i:
                    break
                if s[i] == t[j]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[-1][-1]