【Leetcode72】编辑距离（动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Leetcode72】编辑距离（动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、题目描述

编辑距离动态规划,# 动态规划,LeetCode,动态规划,算法,LeetCode

二、思路

（1）确定状态
dp[i][j]表示word1中前i个单词，变换到word2中前j个字符，最少需要的动作次数。

（2）状态转移方程
编辑距离可以通过以下三种操作进行计算：插入一个字符、删除一个字符、替换一个字符。因此，可以使用以下状态转移方程：

如果 A[i] == B[j]，那么 dp[i][j] = dp[i - 1][j - 1]：即两个当前位置的字符都相同，两种状态的编辑距离都是相等的。
否则，p[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1（实际代码中要用两个min嵌套哦），即取了替换、增加、删除操作编辑距离的最小值，这三种情况和当前情况编辑距离相差1，这个1就是指三种动作各执行1次所能带动的状态转移。

（3）边界+初始条件
边界：如果word1和word2其中一个没字母，即dp[0][j]和dp[i][0]是边界情况，值分别为j和i，即一路加到底和一路减到底。
初始条件：也只有两个字符串都相同或者都是空时编辑距离才为0，先全都将dp赋值为0好了。

（4）计算顺序
根据状态转移方程，下标大的dp值都能从下标小的dp值计算得到，所以i和j都是从小到大遍历。文章来源地址https://www.toymoban.com/news/detail-655954.html

三、C++代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size();
        int m = word2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i <= n; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= m; j++){
            dp[0][j] = j;
        }
        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]), dp[i - 1][j]) + 1;
                }
            }
        }
        return dp[n][m];
    }
};