思路

1. dp数组定义：0_i-1的word1转换成0_j-1的word2需要的最小操作步数为dp[i][j]
2. 递推公式：

   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, min(dp[i-1][j-1] + 1, dp[i][j-1] + 1));
   }

   i-1代表不看当前的i所以是删除；j-1代表不看当前的j所以是替换；二者同时减一说明是插入一个新的

3. dp数组初始化：

   for(int i = 0; i <= word1.size(); i++){dp[i][0] = i;
   }
   for(int j = 1; j <= word2.size(); j++){dp[0][j] = j;
   }

4. 遍历顺序：顺序
5. 时间复杂度：      

代码

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 = 1; 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, min(dp[i-1][j-1] + 1, dp[i][j-1] + 1));}}}return dp[word1.size()][word2.size()];}
};