dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式:

  1. 如果word1[i-1] = word2[j-1]dp[i][j] = dp[i-1][j-1]
  2. 如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j] + 1)
  3. 基准1: dp[0][k] = k
  4. 基准2: dp[k][0] = k

状态公式的解释如下:

  1. 如果word1的第i个字符和word2的第j个字符相等,那么最小编辑距离等于dp[i-1][j-1]的最小编辑距离
  2. 如果word1的第i个字符和word2的第j个字符不相等,那么最小编辑距离等于如下值中的最小者:
    1. word1的前i-1个字符到word2的前j-1个字符所需编辑距离+1(插入)
    2. word1的前i-1个字符到word2的前j个字符所需编辑距离+1(删除)
    3. word1的前i个字符到word2的前j-1个字符所需编辑距离+1(插入)
  3. 基准1: 如果word1为空,那么到word2的编辑距离为word2的长度(持续插入)
  4. 基准2: 如果word2为空,那么到word2的编辑距离为word1的长度(持续删除)

判断是否适用动态规划解法的两个直观条件——a.当前状态和前面状态相关、b.存在基准条件

代码如下:

非常重要:注意搞清楚word1[i]/word2[j]中i/j以及dp[i][j]中i/j的区别,否则循环的边界条件及表达式极容易出问题

//
// Created by jt on 2020/8/30.
//
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     *
     * @param word1 string字符串
     * @param word2 string字符串
     * @return int整型
     */
    int minDistance(string word1, string word2) {
        // write code here
        vector<vector<int> > dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i = 1; i <= word1.size(); ++i) dp[i][0] = i;
        for (int i = 1; i <= word2.size(); ++i) dp[0][i] = i;
        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], dp[i][j-1])) + 1;
            }
        }
        return dp[word1.size()][word2.size()];
    }
};