1. 判断子序列

代码随想录：原文

力扣题目：392.判断子序列

1.1 思路

动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义

• dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]

2. 确定递推公式

• if (s[i - 1] == t[j - 1])： t中找到了一个字符在s中也出现了
  • dp[i][j] = dp[i - 1][j - 1] + 1;
• if (s[i - 1] != t[j - 1])：相当于t要删除元素，继续匹配
  • dp[i][j] = dp[i][j - 1];

和 最长公共子序列的递推公式基本那就是一样的，区别就是本题如果删元素一定是字符串t，而 最长公共子序列 是两个字符串都可以删元素

3. dp数组如何初始化

• dp[i][0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0.
• dp[0][j]同理

4. 确定遍历顺序

• 从上到下，从左到右

5. 举例推导dp数组

• 输入：s = “abc”, t = “ahbgdc”，dp状态转移图如下：

1.1 代码实现

class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); j++) {
                if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = dp[i][j - 1];
            }
        }
        if (dp[s.size()][t.size()] == s.size()) return true;
        return false;
    }
};

2. 不同的子序列

代码随想录：原文

力扣题目：115.不同的子序列

2.1 思路

动规五部曲

1. 确定dp数组（dp table）以及下标的含义

• dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]

2. 确定递推公式

• 当s[i - 1] 与 t[j - 1]相等时：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
• 当s[i - 1] 与 t[j - 1]不相等时：dp[i][j] = dp[i - 1][j];

3. dp数组如何初始化

• dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数：1
• dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数：0

vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; // 其实这行代码可以和dp数组初始化的时候放在一起，但我为了凸显初始化的逻辑，所以还是加上了。

4. 确定遍历顺序

从上到下，从左到右

for (int i = 1; i <= s.size(); i++) {
    for (int j = 1; j <= t.size(); 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];
        }
    }
}

5. 举例推导dp数组

以s：“baegg”，t："bag"为例，推导dp数组状态如下

2.2 代码实现

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
        for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
        for (int j = 1; j < t.size(); j++) dp[0][j] = 0;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 1; j <= t.size(); 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[s.size()][t.size()];
    }
};