對(duì)于大多數(shù)學(xué)習(xí)編程的人來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃一直是一個(gè)難突破的點(diǎn)，我自己在學(xué)習(xí)過(guò)程中也是很困惑，各種書(shū)籍資料，視頻都看過(guò)不少，基本的思想也都能理解，但一碰到題目的時(shí)候還是覺(jué)得無(wú)從下手。最近在做筆試題的時(shí)候突然有了一丟丟理解，這里記錄下， 沒(méi)準(zhǔn)路過(guò)看到的人能加深理解或有所啟發(fā)。

逆向思維

題目如下：

一個(gè)人在 m×n 的方格里行走，每次只能向右或向下，每個(gè)方格里的值是距離，求從起點(diǎn)走到終點(diǎn)的最短路徑值。
示例：3 3
1 3 1
1 5 1
4 2 1
最終輸出 7 ，從左上走到右下所花費(fèi)的最短距離是 7

第一眼看到題目的時(shí)候，就知道是動(dòng)態(tài)規(guī)劃類(lèi)的題了，然而在做題時(shí)由于各（tai）種（cai）原（le）因還是沒(méi)能做出來(lái)，盡管對(duì)這種類(lèi)型的題目見(jiàn)得多了。有種我熟悉它它卻不待見(jiàn)我的趕腳。等到結(jié)束之后回過(guò)頭來(lái)想，想啊想啊想 ... 半小時(shí)過(guò)去了，又想啊想，總算是把代碼實(shí)現(xiàn)出來(lái)了。

按照正常思維來(lái)看的話，人站在起點(diǎn)處，向右或向下走到終點(diǎn)，那么最短距離就是每次比較向左或向下的路程，取最小的走，在加上自身需要的路程，這樣一直走到終點(diǎn)就是最短的路徑值。對(duì)照著題目驗(yàn)證下，那就是 1 -> (向下) 1 -> (向下) 4 -> (向右) 2 -> (向右) 1 到達(dá)終點(diǎn)，總距離是 9 ，發(fā)現(xiàn)這種走法是錯(cuò)的。正確的走法應(yīng)該是 1 -> 3 -> 1 -> 1 -> 1 ,總距離是 7 最短。

image

此方法不行，那我們來(lái)考慮第二種解法?，F(xiàn)在，不從起點(diǎn)來(lái)推算了，因?yàn)槲覀円谎劭催^(guò)去題目這個(gè)矩陣，就知道在這個(gè)輸入下，最好的路徑就是 1 -> 1 -> 1 -> 3 -> 1 這樣走法，怎么得出來(lái)的呢？我們從矩陣最后一個(gè)數(shù)看，它是終點(diǎn)，那這個(gè)終點(diǎn)是如何過(guò)來(lái)的呢？ 發(fā)現(xiàn)它是由左邊或者上邊這個(gè)數(shù)字過(guò)來(lái)的，為什么會(huì)這樣？因?yàn)轭}目說(shuō)了，只能向右或向下走，所以終點(diǎn)的這個(gè)位置要么是上面位置向下走得來(lái)的，要么就是左邊位置向右走到達(dá)的。所以我們從后往前推得出 1 -> 1 -> 1 -> 3 -> 1 這種最佳走法。如下圖：

image

這就是傳說(shuō)中的動(dòng)態(tài)規(guī)劃 , 在這道題里，我們定義的一個(gè)狀態(tài)是 f(i, j) ，表示從起點(diǎn)走到坐標(biāo)（i, j） 所經(jīng)歷的最短路徑，由上面的推斷可以發(fā)現(xiàn)，坐標(biāo) （i,j）的最短路徑總是由 坐標(biāo)(i-1, j) 和坐標(biāo) (i, j-1) 兩個(gè)的最小值加上坐標(biāo) (i, j) 自身的值得來(lái)，
狀態(tài)轉(zhuǎn)移方程為 f(i, j) = Math.min(f(i-1 ,j), f(i, j-1)) + values[i, j] i, j 為二維數(shù)組的坐標(biāo)，values 為數(shù)組對(duì)應(yīng)坐標(biāo)的初始值。原始數(shù)組 values 和 dp 數(shù)組的推算值如下圖：

image

有了上面的鋪墊，我們就可以得出代碼了：

function solve(arr, m, n) {
    //定義一個(gè)二維數(shù)組 dp , dp[i][j]表示走到i,j這個(gè)點(diǎn)的最短路徑
    var dp = new Array(m);
    for (var i = 0; i < m; i++) {
        dp[i] = [];
        for (var j = 0; j < n; j++) {
            dp[i][j] = 0;
        }
    }
    // 初始化第一行和第一列的狀態(tài)值
    dp[0][0] = arr[0][0];
    for (var i = 1; i < n; i++) {
        dp[0][i] = arr[0][i] + dp[0][i - 1];
    }
    for (var i = 1; i < m; i++) {
        dp[i][0] = arr[i][0] + dp[i - 1][0];
    }
    // 動(dòng)態(tài)規(guī)劃，計(jì)算每個(gè)點(diǎn)的最短路徑值
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            dp[i][j] = arr[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

我們用一個(gè)二維數(shù)組dp , 來(lái)存儲(chǔ)每個(gè)節(jié)點(diǎn)的最短路徑值，這里要特別注意的是，需要對(duì)數(shù)組的第一行和第一列進(jìn)行初始化，第一行的每個(gè)點(diǎn)只能由左邊向右走過(guò)來(lái)，所以直接累加相應(yīng)坐標(biāo)的值；同理第一列的每個(gè)點(diǎn)只能由上面向下走得來(lái)，每個(gè)點(diǎn)由原來(lái)的值加上一個(gè)點(diǎn)的值即可。接下來(lái)從第 1 行，第1列開(kāi)始，一直遍歷到 m -1, n -1 ,把每個(gè)狀態(tài)值填上，函數(shù)的返回值為走到終點(diǎn)的坐標(biāo)也就是 dp[m-1][n-1] 。

動(dòng)態(tài)規(guī)劃的思想

在學(xué)習(xí)動(dòng)態(tài)規(guī)劃的時(shí)候，學(xué)的一愣一愣的，什么最優(yōu)子結(jié)構(gòu)、無(wú)副作用、重復(fù)子問(wèn)題等，看著這些理論似懂非懂。

什么是動(dòng)態(tài)規(guī)劃？我覺(jué)得動(dòng)態(tài)規(guī)劃就是逆向，由后往前地去推導(dǎo)這樣的過(guò)程，就仿佛開(kāi)了上帝視角一樣，在已經(jīng)知道結(jié)果的情況下，通過(guò)對(duì)各種情況的抉擇，去倒推出原始的起點(diǎn)，然后定義一個(gè)合理的狀態(tài)來(lái)解釋。像上面的這道題目，問(wèn)你一個(gè)人從左上角走到右下角的最短路程，那我們?cè)诳搭}的時(shí)候，可以全局地看到各個(gè)路徑的距離值以及周?chē)穆窂椒植?，所以可以通過(guò)推算很快得出結(jié)果。上面的第一種解法其實(shí)就是貪心的思路，從起點(diǎn)開(kāi)始，每次選擇一條最短的路徑走下去，這樣帶來(lái)的弊端就是可能后面的路徑是更加糟糕的，容易因?yàn)槎桃暥貌坏阶罴训慕Y(jié)果。

總的來(lái)說(shuō)，在遇到一些求最佳問(wèn)題時(shí)，比如求最短路徑，最大價(jià)值、最長(zhǎng)公共子序列等問(wèn)題時(shí)，就要考慮使用動(dòng)態(tài)規(guī)劃來(lái)求解，而有些時(shí)候，不妨先用貪心的思想來(lái)試試能否求得結(jié)果，這樣也能明白不行的原因在哪里，也能加深對(duì)動(dòng)態(tài)規(guī)劃的應(yīng)用場(chǎng)景理解。

后記

很多時(shí)候看懂了不一定真的懂了，正如開(kāi)頭提到的知道題目是動(dòng)態(tài)規(guī)劃，但就是覺(jué)得無(wú)從下手，現(xiàn)在看還是要多做多理解，也許過(guò)段時(shí)間又有新的領(lǐng)悟。

對(duì)這個(gè)知識(shí)點(diǎn)的理解還有待加深，文章有什么不對(duì)之處，敬請(qǐng)指正，歡迎交流探討。

(完)