181、【动态规划】leetcode ——72. 编辑距离（C++版本）

题目描述

原题链接：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]，直接由上一步转移过来。不相等时，可能会进行三种操作：

1. 增：dp[i][j - 1]要保持word1中0~i-1和word2中0~j-2相等后，再在word1的后面加上一个数，使其和word2中的j-1相等，也就是dp[i][j - 1] + 1加上一步增加操作。
2. 删：dp[i - 1][j]要保持word1中0~i-2和word2中0~j-1相等后，让word1中第i个位置的元素删除，也就是dp[i - 1][j] + 1加上一步删除操作。
3. 改：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. 编辑距离