中华住房与城乡建设厅网站发广告推广平台
题目描述
原题链接：72. 编辑距离
解题思路
- 动态规划五步曲：
（1）dp[i][j]含义： 以word1[i - 1]和word2[j - 1]结尾子串，经过最少次增删改后，可让word1变为word2的步数。dp中的i对应word1中的i-1，dp中的j对应word2中的j-1。
（2）递推公式： word1[i-1]==word2[j-1]时，dp[i][j] = dp[i - 1][j - 1]，直接由上一步转移过来。不相等时，可能会进行三种操作：
- 增：
dp[i][j - 1]要保持word1中0~i-1和word2中0~j-2相等后，再在word1的后面加上一个数，使其和word2中的j-1相等，也就是dp[i][j - 1] + 1加上一步增加操作。 - 删：
dp[i - 1][j]要保持word1中0~i-2和word2中0~j-1相等后，让word1中第i个位置的元素删除，也就是dp[i - 1][j] + 1加上一步删除操作。 - 改：
dp[i - 1][j - 1]要保持word1中0~i-2和word2中0~j-2相等后，再将word1的i-1处的元素改变，使其和word2的j-1处元素相等，也就是dp[i - 1][j - 1] + 1加上一个改变操作。
（3）dp数组初始化： dp[i][0] = dp[0][i] = i，另一方为0时需要删除i次或修改i次。
（4）遍历顺序： 从左到右，从上到下。
（5）举例：
class Solution {
public:int minDistance(string word1, string word2) {int n = word1.size(), m = word2.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for(int i = 0; i <= n; i++) dp[i][0] = i;for(int i = 0; i <= m; i++) dp[0][i] = i;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; 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[n][m];}
};
参考文章：72. 编辑距离