给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
分析:
首先明确两点,
- 在操作字符串的过程中，不可能执行插入某个字符然后又把它删除的操作，这样只会徒增2次操作。
- 在执行增删改字符的过程中，顺序是无关紧要的，所以我们默认从左到右执行操作。
dp[i][j]:把s1[1..i]变为s2[1...j]从左到右所需要的最少操作数（1...i表示下标从1到i）
在思考转移方程时，一般只考虑最后一步
情况1：删除s1的末尾字符s1[i]后，两者相等。
dp[i][j] = dp[i-1][j] + 1
情况2：在s1的末尾增加字符s2[j]后，两者相等。
dp[i][j] = dp[i][j-1] + 1
情况3：在s1的末尾修改字符后，两者相等。
如果s1[i] == s2[j] , 那么无需修改这个字符。
dp[i][j] = dp[i-1][j-1]
如果s1[i] != s2[j] ，需要修改字符s1[i]为s2[j],操作数+1
dp[i][j] = dp[i-1][j-1] + 1
在s2的末尾进行操作的过程和上面一样。
转移方程:
dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + (s1[i] != s2[j]) )
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
//字符串下标从1开始
word1 = " " + word1;
word2 = " " + word2;
int dp[n+1][m+1];
//dp[i][j]:把s1[1--->i]变为s2[1--->j]从左到右操作所需要的最少… }
}
return dp[n][m];
}
};