本文主要是介绍代码训练营第58天：动态规划part16｜leetcode583两个字符串的删除操作｜leetcode72编辑距离。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
leetcode583：两个字符串的删除操作
文章讲解：leetcode583
leetcode72：编辑距离
文章讲解：leetcode72
目录
1，leetcode583 两个字符串的删除操作：
2，leetcode72 编辑距离：
1，leetcode583 两个字符串的删除操作：
做题做到现在发现往往是题目的要求就是dp的含义。不用想的太复杂。两个字符串，这是一个二维dp。dp[i][j]的含义是字符串a到i，字符串b到j为止，需要删除的最少操作。那无非是两种，若i与j相同，就是dp[i][j]=dp[i-1][j-1]，如果不同的，那就删i：dp[i-1][j]+1， 删j：dp[i][j-1], 或者i,j 都删掉：dp[i-1][j-1]+2，这三个取最小即可。注意前天的题目，从1开始遍历，初始化很方便。
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(); 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][j-1]+1, dp[i-1][j]+1);dp[i][j] = min(dp[i][j], dp[i-1][j-1]+2);}}}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，leetcode72 编辑距离：
我的想法是，和上面那道题一样的，如果字母相同，就不用改，如果字母不同，就删一个dp[i-1][j]+1，增加一个dp[i][j-1]+1，或者换一个dp[i-1][j-1]+1
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();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);dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1);}}}return dp[word1.size()][word2.size()];}
};拿下。
这篇关于代码训练营第58天：动态规划part16｜leetcode583两个字符串的删除操作｜leetcode72编辑距离。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
