这道题应该算是编辑距离的入门题目
此类问题的关键就在于递推公式如何推导，分两种大的情况
动态规划五部曲分析如下：
class Solution {
public:
bool isSubsequence(string s, string t) {
if (s.size() > t.size()) return false;
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;
}
};
当s[i – 1] 与 t[j – 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i – 1]来匹配，那么个数为dp[i – 1][j – 1]。
一部分是不用s[i – 1]来匹配，个数为dp[i – 1][j]。
为什么还要考虑 不用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。
所以当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]只有一部分组成，不用s[i – 1]来匹配，即：dp[i – 1][j]
所以递推公式为：dp[i][j] = dp[i – 1][j];
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 i = 1; i < t.size(); i++) dp[0][i] = 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()];
}
};
Original: https://blog.csdn.net/weixin_44047621/article/details/128421970
Author: 小刘很ok
Title: 代码随想录算法训练营第五十五天|392.判断子序列、115.不同的子序列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/777386/
转载文章受原作者版权保护。转载请注明原作者出处！