力扣每日一题115：不同的子序列

题目

困难

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 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 由英文字母组成

面试中遇到过这道题?

1/5

是

否

通过次数

177K

提交次数

340.8K

通过率

51.9%

思路

注意！这是一道hard题！

看到xxx序列在xxx序列中xxx的个数、序列的最长xxx子序列、最长xxx串，最短xxx串这些题目，一眼就想到动态规划。

序列t在序列s的子序列中出现的次数，出现了两个序列的匹配，毫无疑问是二维dp，我们采用由前向后dp的思路，dp[i][j]来表示 t[1:i] 在 s[1:j] 的子序列中出现的次数。注意！由于动态规划一般要对边界值进行讨论，dp的下标从[1][1]开始，[0][……]和[……][0]用来做边界值的讨论。

对于这种两个字符串的动态规划，一般都是讨论 [i] 和 [j] 各自对应的字符是否相等来分类。

状态转移

1、如果t[i-1]!=s[j-1]，也就是 i 对应的字符和 j 对应的字符不相等的情况。

要实现 t[1:i] 和 s[1:j] 的匹配，因为两部分切片的最后一个字符不相等，所有只能祈求 t[1:i] 能不能和 s[1:j-1] 能不能匹配。 $\therefore$ dp[i][j]=dp[i][j-1]。

2、t[i-1]==s[j-1]

两部分切片的最后一个字符相等，所以我们既可以选择两种匹配方法

a、t[i-1] 和 s[j-1] 匹配完成后，t[1:i-1]和t[1:j-1]匹配，这一部分的方案数量是 dp[i-1][j-1]

b、t[i-1]不和s[j-1]匹配，这时就和t[i-1]!=s[j-1]一样，这一部分方案数量就是 dp[i][j-1]

$\therefore$ dp[i][j]=dp[i-1][j-1]+dp[i][j-1]

边界情况的讨论。

状态转移方程中，我们要用到dp[i-1][j-1]，而我们的状态转移的循环是

        for(int i=1;i<=m;i++){for(int j=i;j<=n;j++){if(t[i-1]!=s[j-1]){dp[i][j]=dp[i][j-1];}else{//t[i-1]和s[j-1]匹配+t[i-1]不和s[j-1]匹配dp[i][j]=dp[i-1][j-1]+dp[i][j-1];}}}

m是t串的长度,n是s串的长度。

从循环上看，j<i||i==0 这一部分是没有出现在循环里的，但是i-1和j-1能遍历到，所以我们必然要讨论。

i=0时，代表切片为空串，空串是任何串的子串，所以这一部分的初值为1。

j<i时，s串长度小于t串，这是不可能是子串，所以这一部分初值为0。

        vector<vector<unsigned long long>> dp(m+1,vector<unsigned long long>(n+1,0));//边界情况-->空字符串是任何字符串的子序列for(int i=0;i<=n;i++){dp[0][i]=1;}

代码（注意数据范围和取模）

class Solution {
public:const int mod=1e9+7;int numDistinct(string s, string t) {int n=s.length();int m=t.length();if(n<m) return 0;//dp[i][j]-->t[1-i]在s[1-j]中出现的次数（）//防止边界条件判断，从[1][1]开始算//long long都会超出数据范围vector<vector<unsigned long long>> dp(m+1,vector<unsigned long long>(n+1,0));//边界情况-->空字符串是任何字符串的子序列for(int i=0;i<=n;i++){dp[0][i]=1;}for(int i=1;i<=m;i++){for(int j=i;j<=n;j++){if(t[i-1]!=s[j-1]){dp[i][j]=dp[i][j-1];}else{//t[i-1]和s[j-1]匹配+t[i-1]不和s[j-1]匹配dp[i][j]=dp[i-1][j-1]+dp[i][j-1];}}}int ans=dp[m][n]%mod;return ans;}
};