這是一道相當(dāng)經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題铆铆，最初做這道題的時(shí)候，還是在大學(xué)丹喻，當(dāng)時(shí)見(jiàn)到這題一頭霧水薄货，看了別人的解析還是不太理解，而且看狀態(tài)方程時(shí)碍论，僅僅是看到了狀態(tài)的方程的 “形”谅猾，不懂每個(gè)狀態(tài)方程的本質(zhì)是什么。
如今再做時(shí)骑冗，很快就理解了赊瞬。廢話有點(diǎn)多，不過(guò)認(rèn)真看下去贼涩，相信你會(huì)理解的更深一些巧涧。
在做動(dòng)態(tài)規(guī)劃時(shí)，往往開(kāi)的dp數(shù)組遥倦，有的題是原始數(shù)據(jù)長(zhǎng)度 + 1谤绳，有的不加一
int sovle(int n) {
//n可以理解為題目給的原始數(shù)組長(zhǎng)度，比如斐波那契數(shù)列數(shù)列袒哥，n 表示 第 n 個(gè)值是多少
//然后根據(jù) n 毫無(wú)猶豫的 定義 dp數(shù)組
int[] dp = new int[n];
//有的題目則是如下形式的
int[] dp = new int[n+1];
}
我覺(jué)得要想對(duì)一個(gè)dp狀態(tài)轉(zhuǎn)移方程理解更深刻缩筛，就首先對(duì)dp數(shù)組的定義理解透徹，包括dp數(shù)組長(zhǎng)度是+1還是-1堡称。
體會(huì)到了這一點(diǎn)瞎抛，不管你看別人的題解還是自己想dp方程都能在短時(shí)間內(nèi)把握要點(diǎn)。
拿這道題來(lái)說(shuō)却紧，狀態(tài)方程為 dp[i][j]桐臊，i, j 分別對(duì)應(yīng) word1胎撤，word2兩個(gè)字符串的下標(biāo)。
dp數(shù)組意思為：將 word1 前 i 個(gè)字符 替換成 word2 前 j個(gè)字符断凶，所需的最少步數(shù)伤提。
注意這里的 “前” 字，理解了這個(gè)字认烁，整個(gè)dp轉(zhuǎn)移方程你就掌握了最精髓的一部分肿男。
對(duì)于本題來(lái)說(shuō)：
int len1 = word1.length();
int len2 = word2.length();
/**
如果定義成 len1 len2，就會(huì)有問(wèn)題却嗡。數(shù)組遍歷的下標(biāo)范圍是 [0...len1-1] [0...len2-1 ]
假設(shè)此時(shí)有這樣兩個(gè)單詞
word1: "abcde"
word2: "abc"
同時(shí)遍歷到兩個(gè)字符串的最后一個(gè)位置時(shí)舶沛，根據(jù)dp數(shù)組定義可得：
word1的前4個(gè)字符 變成 word2的前2個(gè)字符，所需的步數(shù)稽穆。
這時(shí)問(wèn)題出現(xiàn)了冠王，len(word1) = 5, len(word2) = 3， 遍歷到最后一個(gè)位置是不是都少了1個(gè)字符舌镶，因?yàn)槭窍聵?biāo)所以取不到完整數(shù)組長(zhǎng)度柱彻。正確的定義應(yīng)該是：word1的前5個(gè)字符 變成 word2的前三個(gè)字符，所需的最小步數(shù)餐胀。
因此正確的定義是: int[][] dp = new int[len1+1][len2+1];
**/
int[][] dp = new int[len1][len2];
步入正題哟楷，構(gòu)建dp狀態(tài)方程
1. 插入一個(gè)字符
2. 刪除一個(gè)字符
3. 替換一個(gè)字符
三個(gè)操作分別對(duì)應(yīng)三個(gè)dp狀態(tài)方程。根據(jù)dp數(shù)組定義否灾，word1 前 i 個(gè)字符 替換成 word2 前 j個(gè)字符卖擅，所需的最少步數(shù)。
假設(shè)現(xiàn)在遍歷到了 word1的 i 位置墨技，word2的 j 位置惩阶。
- 如果 word1[i] == word2[j]，則 dp[i][j] = dp[i-1][j-1] + 0扣汪，因?yàn)楫?dāng)前位置兩個(gè)字符相等断楷，不需要任何操作，狀態(tài)可直接由前一個(gè)狀態(tài)轉(zhuǎn)移而來(lái)崭别。
- 如果 word1[i] == word2[j]冬筒，要分三種情況討論，即茅主，是插入 刪除 or 替換
word1: - - - s
word2: - - e
word1[3] != word2[2]
插入：
在word1后插入一個(gè)字符 e, 即 word1：- - - s e舞痰，就可以與word2最后一個(gè)字符匹配了。word1插入一個(gè)字符 e 之后诀姚，與word2最后一個(gè)位置的 相抵消了响牛。
這時(shí)的狀態(tài)方程為: dp[i][j] = dp[i][j-1] + 1。為什么 是 j-1? 因?yàn)?i 插入的那個(gè)字符與 j 位置的字符抵消了。
刪除：
因?yàn)?i 位置 與 j 位置 不匹配娃善，這時(shí)也可以選擇將 i 位置刪除论衍，有的人可能會(huì)問(wèn)，既然不匹配聚磺，為什么不刪除 j 位置呢? 這時(shí)回到dp數(shù)組的本身含義：將 word1前 i 個(gè) 替換成word2 前j個(gè)
。 前者 即 word1屬于主動(dòng)做事情的一方炬丸，所以刪除 i 位置瘫寝，這時(shí)狀態(tài)方程為: dp[i][j] = dp[i-1][j] + 1。加1表示稠炬，進(jìn)行了一次刪除操作焕阿。
插入:
可將 word1的 i 位置字符替換成 j 位置的e， 這樣兩個(gè)位置就匹配了：dp[i][j] = dp[i-1][j-1] + 1首启。
具體細(xì)節(jié)參見(jiàn)源碼：
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];
/**
從有到無(wú)
初始化條件：將word1的前 i個(gè)字符替換成word2的 前0個(gè)字符所需要的步數(shù)
即：在word1中進(jìn)行刪除操作
**/
for(int i = 0; i < len1 + 1; i++) {
dp[i][0] = i;
}
//添加操作 從無(wú)到有
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];
}
