392.判断子序列

题目链接：392.判断子序列
与1143.最长公共子序列 几乎相同

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

将dp数组压缩至一维，有

class Solution {
public:bool isSubsequence(string s, string t) {vector<int> dp(t.size() + 1, 0);for (int i = 1; i < s.size() + 1; ++i) {int prev = 0;for (int j = 1; j < t.size() + 1; ++j) {int temp = dp[j]; // 保存当前 dp[j] 的值dp[j] = (s[i - 1] == t[j - 1])? prev + 1: max(dp[j], dp[j - 1]);prev = temp; // 更新 prev}}return dp.back() == s.size();}
};

对于每个位置 (i, j)，其中 i 代表字符串 s 的索引，j 代表字符串 t 的索引，计算 dp[j] 的值。具体做法如下：

• 如果 s[i - 1] 等于 t[j - 1]，即当前字符匹配，则 dp[j] 的值等于 prev + 1，其中 prev 是上一个位置 (i - 1, j - 1) 的值。
• 如果 s[i - 1] 不等于 t[j - 1]，即当前字符不匹配，则 dp[j] 的值等于 dp[j] 和 dp[j - 1] 中的较大值。dp[j - 1] 是上一行对应位置的值，即(i, j - 1)

为了在计算新值之前保存 dp[j] 的旧值，使用变量 temp。

---

115.不同的子序列

题目链接：115.不同的子序列
可以当做删除s中其他元素，有多少种和t相同的个数。

dp数组 ： 以i - 1为结尾的s中有以j - 1为结尾的t的个数为dp[i][j]个

递推公式：

dp[i][j] = (s[i - 1] == t[j - 1])? dp[i - 1][j - 1] + dp[i - 1][j]: dp[i - 1][j];

dp[i - 1][j - 1] + dp[i - 1][j]

• dp[i - 1][j - 1] 相当于s变成i - 2结尾，删除了第i - 1个元素
• dp[i - 1][j]这个情况就是题目中所描述的情况，比如s是bagg，t是bag。可以有s中ba_g和t bag匹配上，dp[i - 1][j - 1]的状态，也可以是s中bag_和t bag匹配上，就是dp[i - 1][j]的状态。

dp[i - 1][j] 删除s的第i - 1个元素，不考虑第i-1个元素。

由于题目中的s和t的地位不同（t是子集，s是全集），因此有dp[i - 1][j]状态出现，而没有dp[i][j - 1]状态出现。

初始化：
二维数组初始化第一行和第一列。
dp[i][0] = 1 t为空字符在s中有1种，dp[0][j] = 0 t在s空字符中有0种
上述两个交集：dp[0][0] = 1 空字符t在空字符s中有1种

class Solution {
public:int numDistinct(string s, string t) {vector<vector<unsigned/*int会溢出*/>> dp(s.size() + 1, vector<unsigned>(t.size() + 1, 0));for (auto& tmp : dp) {tmp[0] = 1;//初始化dp[i][0]}for (int i = 1; i < s.size() + 1; ++i) {for (int j = 1; j < t.size() + 1; ++j) {dp[i][j] = (s[i - 1] == t[j - 1])? dp[i - 1][j - 1] + dp[i - 1][j]: dp[i - 1][j];}}return dp.back().back();}
};

dp数组压缩为一维数组

class Solution {
public:int numDistinct(string s, string t) {vector<unsigned> dp(t.size() + 1, 0);dp[0] = 1;for (int i = 1; i <= s.size(); i++) {int prev = 1;for (int j = 1; j <= t.size(); j++) {int temp = dp[j];if (s[i - 1] == t[j - 1]) {dp[j] = prev + dp[j];}prev = temp;}}return dp.back();}
};

对于每个字符s[i - 1]和t[j - 1]，若它们相等，则可以选择将s[i - 1]与t[j - 1]匹配，此时，我们需要在s的前i - 1个字符和t的前j - 1个字符中找到不同子序列的个数，即dp[j - 1]。同时，我们还可以选择不将s[i - 1]与t[j - 1]匹配，此时，我们需要在s的前i - 1个字符和t的前j个字符中找到不同子序列的个数，即dp[j]。因此，当前字符的不同子序列的个数等于这两种选择的和。

在内层循环中，我们使用prev变量来保存上一次迭代时的dp[j]的值，以便在计算dp[j]时使用。这样可以确保计算当前字符的不同子序列的个数时，使用的是上一次迭代时的值而不是当前迭代时的值。

---