115.不同的子序列
但相对于刚讲过 392.判断子序列,本题 就有难度了 ,感受一下本题和 392.判断子序列 的区别。
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()];
}
};
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<long long>>dp(s.size()+1,vector<long long>(t.size()+1,0));
long long mod=10e9+7;
for (int i=0;i<s.size();i++)dp[i][0]=1;
for (int i=1;i<s.size()+1;i++){
for (int j=1;j<t.size()+1;j++){
if (s[i-1]==t[j-1])dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%mod;
else dp[i][j]=dp[i-1][j]%mod;
}
}
return dp[s.size()][t.size()];
}
};
总结
想了半天,结果还是没有什么思路。
583. 两个字符串的删除操作
本题和动态规划:115.不同的子序列 相比,其实就是两个字符串都可以删除了,情况虽说复杂一些,但整体思路是不变的。
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i=1;i<=word1.size();i++){
for (int j=1;j<=word2.size();j++){
if (word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
int res=dp[word1.size()][word2.size()];
return word1.size()-res+word2.size()-res;
}
};
72. 编辑距离
最终我们迎来了编辑距离这道题目,之前安排题目都是为了 编辑距离做铺垫。
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>>dp(word1.size()+1,vector<int>(word2.size()+1,0));
for (int i=0;i<word1.size()+1;i++)dp[i][0]=i;
for (int j=0;j<word2.size()+1;j++)dp[0][j]=j;
for (int i=1;i<word1.size()+1;i++){
for (int j=1;j<word2.size()+1;j++){
if (word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];
else dp[i][j]=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})+1;
}
}
return dp[word1.size()][word2.size()];
}
};
总结
dp[i-1][j-1]+1的情况没有考虑到原来它就是换元素。