代码随想录算法训练营day50|动态规划12
不同的子序列
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。、
编辑距离中的删除元素,其实就是直接变数字,其只删除原来的较长的数组里的元素
递推模拟,使用s的最后一个元素匹配,或者删除最后一个元素看前面一个是否匹配
初始化,dp[i][0]=1表示s不为空,t为空,这样把s删到空就一定有一个,同理dp[0][i]=0,重叠部分dp[0][0]就等于空字符串匹配空字符串,为1
定义为int,出现了超时错误
所以可以用longlongint 的别名 uint64_t
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 minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));
for(int i=0;i<=word1.size();i++) dp[i][0]=i;
for(int j=0;j<=word2.size();j++) dp[0][j]=j;
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];
else dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
}
}
return dp[word1.size()][word2.size()];
}
};
思路二是,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度
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]);
}
}
return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
}
};
编辑距离(动规经典问题)
=为什么这道题不能采用上一题的思路二,先求出公共子序列的长度,再用两个字符串的总长度减去公共子序列的长度,因为很可能长度一样,但可以只替换一次就完成,但思路2会要求按着顺序删除
原文地址:https://blog.csdn.net/Lindsey_feiren/article/details/144303003
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!