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

Love The Way You Lie 2024-04-27 06:41 14阅读 0赞

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

[点击直接跳转到该题目][Link 3]

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣题目解析
 *  3️⃣解题代码

## 1️⃣题目描述 ##

给你两个字符串 `s` 和 t ，统计并返回在 `s` 的 子序列 中 `t` 出现的个数，结果需要对  1 0 9 10^\{9\} 109 \+ 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];
        }
    };

**最后就通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[530b2fdc59bf45d5bfa43fd373793841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b212fcb8221241e483d4cfe155ee31a2.png
[Link 3]: https://leetcode.cn/problems/distinct-subsequences/description/