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

本文主要是介绍【算法|动态规划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];}
};