最小编辑距离

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()];
    }
};