当前位置：首页 > news >正文

036不同的子序列动态规划

news 2026/4/16 19:10:10

115. 不同的子序列

困难

相关企业

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

示例 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 由英文字母组成

class Solution {
public:int numDistinct(string s, string t) {int m = s.size();int n = t.size();//dp[i] [j] :以下标是i-1为结尾的s 中 有以下标是j-1为结尾的t 的个数vector<vector<unsigned long long>> dp(m+1,vector<unsigned long long>(n+1,0));for(int i=0;i<=m;i++){dp[i][0] = 1;  }for(int j=0;j<=n;j++){dp[0][j] = 0;}dp[0][0] = 1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s[i-1]==t[j-1]){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{dp[i][j] = dp[i-1][j];}}}return dp[m][n];}
};

编辑距离类问题
主串中有多少种子序列（可以不连续）
也就是主串中有多少删除字符串的方式，使其变成子串t
用unsigned long long 防止溢出
注意代码随想录中没有初始化=m和=n的时候，也能通过，这是因为
```
dp[i][j] 只依赖：dp[i-1][j-1] 和 dp[i-1][j]
```
永远不会用到 dp[s.size()] [0]，但是逻辑上最好还是要把它初始化了

dp[i] [j] :以i-1为结尾的s有以j-1为结尾的t的个数（二维dp一般都用i-1，一维一般都用i）
递推公式：
初始化：有时候单纯根据定义进行初始化很牵强，可以自己举个例子画矩阵推一下，稍微结合一下定义看看如何初始化能够推出最后答案

由递推公式可以得出，dp[i] [j] 由左边和上边得出（可以画一个矩阵看一看），所以要初始化最左边和最上边 dp[i] [0] = 1 (s串中有多少个空字符串，有一个，当把所有字符全部删掉就是空字符串t) dp[0] [j] = 0 （s是空的，t不是空的，s怎么删也变不成t，所以有0种方法）注意：这里有一个交集，dp[0] [0] = 1:空字符串s有一种方法删成空字符串t

这一类问题，基本是要分析两种情况

s[i - 1] 与 t[j - 1]相等
s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i] [j]可以有两部分组成。

一部分是用s[i - 1]来匹配，那么个数为dp[i - 1] [j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1] [j-1] （这里就是若s 和 t 的最后一个字母相同，就不管两个串的最后一个字母了，就看除了两个串的最后一个字母之外的s中有几个t ，如 s:bagg t:bag ,最后一个g相同，变成bag中有多少个ba，当然这里并不一定非要是最后一个，这个最后一个只是当前遍历的字符，不一定是真正的s和t的最后一个字母）。

一部分是不用s[i - 1]来匹配，个数为dp [i - 1] [j]。（可以不用最后一个字母匹配，比如bagg中不用最后一个g，判断前面的bag中有多少个t：bag也可以）

这里可能有录友不明白了，为什么还要考虑不用s[i - 1]来匹配，都相同了指定要匹配啊。

例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。