20201_022201canvas.png
这是一道相当经典的动态规划问题，最初做这道题的时候，还是在大学，当时见到这题一头雾水，看了别人的解析还是不太理解，而且看状态方程时，仅仅是看到了状态的方程的 “形”，不懂每个状态方程的本质是什么。
如今再做时，很快就理解了。废话有点多，不过认真看下去，相信你会理解的更深一些。
在做动态规划时，往往开的dp数组，有的题是原始数据长度 + 1，有的不加一
int sovle(int n) {
//n可以理解为题目给的原始数组长度，比如斐波那契数列数列，n 表示 第 n 个值是多少
//然后根据 n 毫无犹豫的 定义 dp数组
int[] dp = new int[n];
//有的题目则是如下形式的
int[] dp = new int[n+1];
}
我觉得要想对一个dp状态转移方程理解更深刻，就首先对dp数组的定义理解透彻，包括dp数组长度是+1还是-1。
体会到了这一点，不管你看别人的题解还是自己想dp方程都能在短时间内把握要点。
拿这道题来说，状态方程为 dp[i][j]，i, j 分别对应 word1，word2两个字符串的下标。
dp数组意思为：将 word1 前 i 个字符 替换成 word2 前 j个字符，所需的最少步数。
注意这里的 “前” 字，理解了这个字，整个dp转移方程你就掌握了最精髓的一部分。
对于本题来说：
int len1 = word1.length();
int len2 = word2.length();
/**
如果定义成 len1 len2，就会有问题。数组遍历的下标范围是 [0...len1-1] [0...len2-1 ]
假设此时有这样两个单词
word1: "abcde"
word2: "abc"
同时遍历到两个字符串的最后一个位置时，根据dp数组定义可得：
word1的前4个字符 变成 word2的前2个字符，所需的步数。
这时问题出现了，len(word1) = 5, len(word2) = 3， 遍历到最后一个位置是不是都少了1个字符，因为是下标所以取不到完整数组长度。正确的定义应该是：word1的前5个字符 变成 word2的前三个字符，所需的最小步数。
因此正确的定义是: int[][] dp = new int[len1+1][len2+1];
**/
int[][] dp = new int[len1][len2];
步入正题，构建dp状态方程
1. 插入一个字符
2. 删除一个字符
3. 替换一个字符
三个操作分别对应三个dp状态方程。根据dp数组定义，word1 前 i 个字符 替换成 word2 前 j个字符，所需的最少步数。
假设现在遍历到了 word1的 i 位置，word2的 j 位置。
- 如果 word1[i] == word2[j]，则 dp[i][j] = dp[i-1][j-1] + 0，因为当前位置两个字符相等，不需要任何操作，状态可直接由前一个状态转移而来。
- 如果 word1[i] == word2[j]，要分三种情况讨论，即，是插入 删除 or 替换
word1: - - - s
word2: - - e
word1[3] != word2[2]
插入：
在word1后插入一个字符 e, 即 word1：- - - s e，就可以与word2最后一个字符匹配了。word1插入一个字符 e 之后，与word2最后一个位置的 相抵消了。
这时的状态方程为: dp[i][j] = dp[i][j-1] + 1。为什么 是 j-1? 因为 i 插入的那个字符与 j 位置的字符抵消了。
删除：
因为 i 位置 与 j 位置 不匹配，这时也可以选择将 i 位置删除，有的人可能会问，既然不匹配，为什么不删除 j 位置呢? 这时回到dp数组的本身含义：将 word1前 i 个 替换成word2 前j个
。 前者 即 word1属于主动做事情的一方，所以删除 i 位置，这时状态方程为: dp[i][j] = dp[i-1][j] + 1。加1表示，进行了一次删除操作。
插入:
可将 word1的 i 位置字符替换成 j 位置的e， 这样两个位置就匹配了：dp[i][j] = dp[i-1][j-1] + 1。
具体细节参见源码：
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
if(len1*len2 == 0)
return len1+len2;
int dp[][] = new int[len1+ 1][len2+1];
/**
从有到无
初始化条件：将word1的前 i个字符替换成word2的 前0个字符所需要的步数
即：在word1中进行删除操作
**/
for(int i = 0; i < len1 + 1; i++) {
dp[i][0] = i;
}
//添加操作 从无到有
for(int j = 0; j < len2 + 1; j++) {
dp[0][j] = j;
}
for(int i = 1; i < len1 + 1; i++) {
for(int j = 1; j < len2 + 1; j++) {
int insert = dp[i][j-1] + 1;
int delete = dp[i-1][j] + 1;
int replace = dp[i-1][j-1];
if(word1.charAt(i-1) != word2.charAt(j-1)) {
replace += 1;
}
dp[i][j] = Math.min(insert, Math.min(delete, replace));
}
}
return dp[len1][len2];
}
