力扣-动态规划-583两个字符的删除操作

思路 dp数组定义：0_i-1的字符串和0_j-1的字符串删除到相等时的最小步数递推公式： if(word1[i-1] == word2[j-1]){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1; }

如果相同时，代表不删除元素就行；不同时，需要选择删除i或者j中的其中一个元素，并且最小步数加一

dp数组初始化： vector< vector<int> > dp(word1.size() + 1, vector<int>(word2.size() + 1, INT_MAX)); for(int i = 0; i <= word1.size(); i++){ dp[i][0] = i; } for(int j = 0; j <= word2.size(); j++){ dp[0][j] = j; } 遍历顺序：顺序时间复杂度：       代码 class Solution { public: int minDistance(string word1, string word2) { vector< vector<int> > dp(word1.size() + 1, vector<int>(word2.size() + 1, INT_MAX)); 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], dp[i][j-1]) + 1; } } } return dp[word1.size()][word2.size()]; } };