583. 两个字符串的删除操作
思路：
dp[i][j]:以i-1为下标的word1和以j-1为下标的word2，要达到相等需要删除的最小操作次数为dp[i][j]。递推关系：如果nums1[i-1]==nums2[j-1]，此时dp[i][j]=dp[i-1][j-1]；如果nums1[i-1]!=nums2[j-1]，此时有三种情况：1、删word1，dp[i][j]=dp[i-1][j]+1，2、删word2，dp[i][j]=dp[i][j-1]+1，3、删除word1和word2，dp[i][j]=dp[i-1][j-1]+2，以上三个取最小值。4、初始化：由递推关系可以得到需要初始化dp[0][j]和dp[i][0]，由dp数组的含义不难得到dp[0][j]=j，dp[i][0]=i；遍历顺序：从小到大，从前向后。
代码：
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(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
}
}
}
return dp[word1.size()][word2.size()];
}
};
72. 编辑距离
思路：
这道题的整体思路和上面一道题是一致的，只不过这里多了另外的两种操作：增和替换。因为是对一个元素操作，对word1的增加可以理解为对word2的减，而替换是指在word1[i]!=word2[j]的情况下，将word1[i]替换成word2[j]，最少的操作次数就是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(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
}
}
}
return dp[word1.size()][word2.size()];
}
};
