题目描述

给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
你可以对一个单词执行以下3种操作：
a）在单词中插入一个字符
b）删除单词中的一个字符
c）替换单词中的一个字符

解题思路

动态规划问题，简单的思想就是将问题拆分为一个个最小子问题，然后依次解决每个小子问题并从中找到规律。

经过几道动态规划的练习，大概都是通过矩阵来找规律的，不妨先通过矩阵找一下规律：

其中word1为"abc"，word2为"bcac".通过分析可知，第一行和第一列依旧是特殊的。然后从非第一行和第一列处发现（非绿色区域），发现当前位置两个字符相同时它的值等于左上方的值，即

dp[i][j]=dp[i-1][j-1]；当两个字符不相等时，情况就要复杂一点了。

通过前面动态规划的经验，当前位置的值和它的左、上、左

上会存在一定的关系，而且知道当两个字符不一样时至少需要进行一种操作，对当前位置减一发现是左、上、左上中最小的那个。因此可以得到dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]) + 1;

代码

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.length();// row
        int n = word2.length();// col
        
        vector<vector<int> > dp(m+1, vector<int>(n+1));
        for (int i = 0; i < m + 1; i++) // 初始化第一列
            dp[i][0] = i;
        for (int j = 1; j < n + 1; j++)//初始化第一行
            dp[0][j] = j;
        
        for (int i = 1; i < m + 1; i++)
            for (int j = 1; j < n + 1; j++)
            {
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
            }
        return dp[m][n];
    }
};

参考链接：

https://www.nowcoder.com/questionTerminal/81d7738f954242e5ade5e65ec40e5027?f=discussion