力扣_字符串8—不同的子序列

题目

给你两个字符串 $s$ 和 $t$ ，统计并返回在 $s$ 的 子序列 中 $t$ 出现的个数，结果需要对 $10^9+7$ 取模。

示例：
输入：$s=rabbbit,t=rabbit$
输出：$3$
解释：
如下所示, 有 3 种可以从 $s$ 中得到 $rabbit$ 的方案。

• rabbbit
• rabbbit
• rabbbit

方法

• 动态规划
  • 创建二维 $dp$ 数组， $dp[i][j]$ 表示 $t[0:j-1]$ 在 $s[0:i-1]$ 中出现的次数
  • 状态转移
    • 边界条件：$dp[i][0]=1,dp[0][j]=0$
    • 若 $s[i-1]==t[j-1]$，$s[i-1]$ 可以选择自己是否跟 $t[j-1]$ 匹配
      • $dp[i][j]$ 由两部分组成：
        • 如果匹配，那么 dp[i][j] 其中一部分数量就是 dp[i-1][j-1]
        • 如果选择不匹配（这样可以让前面的字符跟 $t[j-1]$ 匹配)， $dp[i][j]$ 另外一部分就是 $dp[i-1][j]$
    • 若 $s[i-1]!=t[j-1]$，$dp[i][j]=dp[i-1][j]$

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        int n1 = s.size();
        int n2 = t.size();
        vector<vector<int>> dp(n1+1, vector<int>(n2+1));
        for(int i = 0; i < n1; i++)
            dp[i][0] = 1;
        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j])%(1000000000+7);
                }
                else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n1][n2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21