【算法|动态规划No.22】leetcode115. 不同的子序列

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

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

示例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

注意：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

2️⃣题目解析

状态表示：

• dp[i][j]：s字符串[0,i]区间的子串中含有多少个t字符串[0,j]区间内的子串

状态转移方程（根据s字符串中子序列的最后一个位置是否包含s[j]）：

• 包含s[j]时：如果t[i] == s[j]，则dp[i][j] = dp[i - 1][j - 1]
• 不包含s[j]时：dp[i][j] += dp[i ][j - 1]

3️⃣解题代码

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

最后就通过啦！！！