【3.17】LeetCode每日一题· 不同的子序列

2021年03月17日 10时20分

标签： LeetCode 动态规划

## 题目描述
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个**子序列**是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 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
		^^^

#### 提示
	0 <= s.length, t.length <= 1000
	s 和 t 由英文字母组成

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/distinct-subsequences "题目链接")

## 解题思路
动态规划，分类讨论的重要思想。

设`dp[i][j] := s[0..i]的子序列中，t[0..j]出现的个数 `。
1. 如果我们不将`s[i]`和`t[j]`匹配，那么有
		dp[i][j] = dp[i-1][j]
2. 如果我们将`s[i]`和`t[i]`匹配，此时需要满足`s[i] == t[j] `，那么有
		dp[i][j] += dp[i-1][j-1] if s[i] == t[j] else 0

显然，
	
	dp[0][0] = 1 if s[0] == t[0] else 0

当`0 <= i < j `时，`t[0..j]`的长度大于`s[0..j]`的长度，`t[0..j]`不可能包含在`s[0..j]`的子序列中，故
    
	dp[0][0] = 0 if i < j else 0

需要注意的是，空字符串是任何字符串的子序列，因此有对于任意`0 <= i < N`

dp[i][-1] = 1

综上，可以得到代码（Tips：虽然最后答案在32位整数范围之内，但是中间结果可能超出，因此需要使用long long）。

## 代码
```cpp
class Solution {
public:
    // dp[i][j] := s[0..i]的子序列中，t[0..j]出现的个数
    // dp[i][j] = dp[i-1][j] +  (dp[i-1][j-1] if s[i] == t[j] else 0)
    // dp[0][0] = 1 if s[0] == t[0] else 0
    // dp[i][-1] = 1(空字符串包含在任意子序列中)

int numDistinct(string s, string t) {
        const int N = s.length(), M = t.length();
        if(N < M) return 0;
        if(M == 0) return 1;
        vector<vector<long long>> dp(N, vector<long long>(M));
        dp[0][0] = (s[0] == t[0]);
        for(int i = 1; i < N; i++){
            for(int j = 0; j <= min(i, M-1); j++){
                dp[i][j] = dp[i-1][j];
                if(j-1 >= 0){
                    dp[i][j] += (s[i] == t[j]? dp[i-1][j-1]: 0);
                }else{
                    dp[i][j] += (s[i] == t[j]? 1: 0);
                }
            }
        }
        return dp[N-1][M-1];
    }
};
```

### 用时和内存
> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：7.2 MB，在所有 C\++提交中击败了55.19%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.17】LeetCode每日一题· 不同的子序列

所有评论

暂无评论

新增评论