双序列型动态规划——不同的子序列

谁借莪１个温暖的怀抱￠ 2022-10-27 12:07 182阅读 0赞

#  #

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 1：

输入：s = "rabbbit", t = "rabbit"
    输出：3
    解释：
    如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
    (上箭头符号 ^ 表示选取的字母)
    rabbbit
    ^^^^ ^^
    rabbbit
    ^^ ^^^^
    rabbbit
    ^^^ ^^^

### 1、题目分析 ###

B在A中出现多少次（可以不连续）

如果至少出现一次，那么A和B的最长公共子串就是B，而且也不能更长

用最长公共子串的思路：对应对子。但不同的是，B的每一个字符都必须出现在一个对子里。 所以这题的“最后一步”以B为出发点

### 2、确定状态 ###

情况1：B\[n-1\] = A\[m-1\]，结成对子，求B\[0…n-2\]在A\[0…m-2\]中出现多少次

情况2：B\[n-1\]不和 A\[m-1\]结成对子，求B\[0…n-1\]在A\[0…m-2\]中出现多少次

因此，要求B\[0…n-1\]在A\[0…m-1\]中出现多少次；需要知道B\[0…n-1\]在A\[0…m-2\]中出现多少次，以及B\[0…n-2\]在A\[0…m-2\] 中出现多少次

所以可以假设状态f\[i\]\[j\]为B前j个字符B\[0…j-1\]在A前i个字符A\[0…i-1\]中出现多少次

### 3、转移方程 ###

假设状态f\[i\]\[j\]为B前j个字符B\[0…j-1\]在A前i个字符A\[0…i-1\]中出现多少次

![在这里插入图片描述][20210203221900640.png]

### 4、初始条件和边界情况 ###

初始条件：

– 如果B是空串，B在A中出现次数是1

– f\[i\]\[0\] = 1 (i = 0, 1, 2, …, m)

– 如果A是空串而B不是空串，B在A中出现次数是0

– f\[0\]\[j\] = 0 (j = 1, 2, …, n)

### 5、计算顺序 ###

逐行计算，答案是f\[m\]\[n\]

时间复杂度：O(MN)，空间复杂度：O(MN)

### 6、代码实现 ###

class Solution:
        def numDistinct(self, s: str, t: str) -> int:
            n=len(s)+1
            m=len(t)+1
            dp=[[0]*m for i in range(n)]
            for i in range(n):
                for j in range(m):
                    if j>i:
                        break
                    if j==0:
                        dp[i][j]=1
                        continue 
                    if i==0:
                        dp[i][j]=0
                        continue
                    dp[i][j]=dp[i-1][j]
                    if s[i-1]==t[j-1]:
                        dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
            return dp[n-1][m-1]

[20210203221900640.png]: /images/20221024/ea915bf383154d7e98e3d1ff4b5ac6ea.png