代码随想录算法训练营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会要求按着顺序删除