72. 編輯距離

再次驗(yàn)證leetcode的評(píng)判機(jī)有問(wèn)題啊！同樣的代碼，第一次提交超時(shí)，第二次提交就通過(guò)了！

此題用動(dòng)態(tài)規(guī)劃解決。

這題一開(kāi)始還真難到我了，琢磨半天沒(méi)有思路。于是乎去了網(wǎng)上喵了下題解看到了動(dòng)態(tài)規(guī)劃4個(gè)字就趕緊回來(lái)了。

腦海中浮現(xiàn)了兩個(gè)問(wèn)題：
為什么能用動(dòng)態(tài)規(guī)劃呢？用動(dòng)態(tài)規(guī)劃怎么解？

先描述狀態(tài)吧：

f[i][j]表示word1中的[0,i] 與 word2中[0,j]的最少操作數(shù)。

實(shí)際上這時(shí)候就能看出來(lái)了，當(dāng)一個(gè)狀態(tài)計(jì)算完成時(shí)，即一個(gè)狀態(tài)的操作方案（決策）確定時(shí)，不影響后面狀態(tài)的最優(yōu)決策。即滿足動(dòng)態(tài)規(guī)劃要求的無(wú)后效性，否則不能用動(dòng)規(guī)來(lái)解決啦，因?yàn)橐婕暗交厮菪薷那懊娴臎Q策。也就是滿足兩個(gè)條件：1. 重疊子問(wèn)題 2.最優(yōu)子結(jié)構(gòu)

動(dòng)態(tài)規(guī)劃原理
雖然已經(jīng)用動(dòng)態(tài)規(guī)劃方法解決了上面兩個(gè)問(wèn)題，但是大家可能還跟我一樣并不知道什么時(shí)候要用到動(dòng)態(tài)規(guī)劃。總結(jié)一下上面的斐波拉契數(shù)列和鋼條切割問(wèn)題，發(fā)現(xiàn)兩個(gè)問(wèn)題都涉及到了重疊子問(wèn)題，和最優(yōu)子結(jié)構(gòu)。

①最優(yōu)子結(jié)構(gòu)

用動(dòng)態(tài)規(guī)劃求解最優(yōu)化問(wèn)題的第一步就是刻畫(huà)最優(yōu)解的結(jié)構(gòu)，如果一個(gè)問(wèn)題的解結(jié)構(gòu)包含其子問(wèn)題的最優(yōu)解，就稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。因此，某個(gè)問(wèn)題是否適合應(yīng)用動(dòng)態(tài)規(guī)劃算法，它是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)是一個(gè)很好的線索。使用動(dòng)態(tài)規(guī)劃算法時(shí)，用子問(wèn)題的最優(yōu)解來(lái)構(gòu)造原問(wèn)題的最優(yōu)解。因此必須考查最優(yōu)解中用到的所有子問(wèn)題。

②重疊子問(wèn)題

在斐波拉契數(shù)列和鋼條切割結(jié)構(gòu)圖中，可以看到大量的重疊子問(wèn)題，比如說(shuō)在求fib（6）的時(shí)候，fib（2）被調(diào)用了5次，在求cut（4）的時(shí)候cut（0）被調(diào)用了4次。如果使用遞歸算法的時(shí)候會(huì)反復(fù)的求解相同的子問(wèn)題，不停的調(diào)用函數(shù)，而不是生成新的子問(wèn)題。如果遞歸算法反復(fù)求解相同的子問(wèn)題，就稱為具有重疊子問(wèn)題（overlapping subproblems）性質(zhì)。在動(dòng)態(tài)規(guī)劃算法中使用數(shù)組來(lái)保存子問(wèn)題的解，這樣子問(wèn)題多次求解的時(shí)候可以直接查表不用調(diào)用函數(shù)遞歸。

顯然，狀態(tài)轉(zhuǎn)移方程也就出來(lái)了：

f[i][j] 的計(jì)算分為兩種情況：

當(dāng)word1[i] == word2[j] 說(shuō)明此時(shí)不需要任何操作，f[i][j] = f[i-1][j-1]

else f[i][j] = min(f[i-1][j-1] , f[i-1][j] , f[i][j-1] ) + 1 , 此時(shí)，f[i][j] 可由之前已經(jīng)確定的三個(gè)狀態(tài)而來(lái)（因?yàn)橛腥N操作），如果是word1替換操作，則之前的狀態(tài)為f[i-1][j-1]；word1刪除操作,則之前的狀態(tài)為： f[i-1][j]，此時(shí)就是刪除word[i]；word1插入操作,則之前的狀態(tài)為：f[i][j-1]，此時(shí)實(shí)際上就是在word[i]后面插入word2[j]

那初始條件呢？當(dāng)一方為空時(shí)，最少操作數(shù)就是另一個(gè)word的size了

for (int i = 0; i <= m; i++) {f[i][0] = i;}for (int j = 0; j <= n; j++) {f[0][j] = j;}

1A代碼

class Solution {public int minDistance(String word1, String word2) {int m = word1.length();int n = word2.length();if (m == 0) {return n;}if (n == 0) {return m;}int[][] f = new int[m + 1][n + 1];for (int i = 0; i <= m; i++) {f[i][0] = i;}for (int j = 0; j <= n; j++) {f[0][j] = j;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {f[i][j] = f[i - 1][j - 1];} else {f[i][j] = Collections.min(Arrays.asList(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1])) + 1;}}}return f[m][n];} }

轉(zhuǎn)載于:https://www.cnblogs.com/acbingo/p/9369297.html

總結(jié)

以上是生活随笔為你收集整理的[leetcode] 72. 编辑距离(二维动态规划)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。