30分鐘入門(mén)動(dòng)態(tài)規(guī)劃

題目描述

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋?zhuān)阂驗(yàn)槁窂?1→3→1→1→1 的總和最小。

示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= gridi <= 100

題解

此題是典型的動(dòng)態(tài)規(guī)劃題目，可以作為入門(mén)題，不過(guò)要比爬樓梯還要稍微復(fù)雜點(diǎn)。

先來(lái)了解下概念，所謂動(dòng)態(tài)規(guī)劃，本質(zhì)上也是遞歸，找重復(fù)，不過(guò)與遞歸的區(qū)別是要把問(wèn)題分解為最優(yōu)子問(wèn)題，所謂最優(yōu)子問(wèn)題，是指這個(gè)子問(wèn)題大部分情況下可以代表最佳解題思路。如果你知道分治解法，動(dòng)態(tài)規(guī)劃與分治法的區(qū)別就是，分治是為了分而分，不在乎是否最優(yōu)，有可能每個(gè)子問(wèn)題之間有重復(fù)計(jì)算；而動(dòng)態(tài)規(guī)劃就是找到最優(yōu)解，一擊致命地找到最佳解題方案，把一個(gè)復(fù)雜問(wèn)題分解為若干子問(wèn)題，每個(gè)子問(wèn)題是相互獨(dú)立的，最后把這些子問(wèn)題的值合并，得到最終解。

就這個(gè)問(wèn)題來(lái)說(shuō)，要從左上角走到右下角，要找一條路徑上的數(shù)值和為最小的路。再直白點(diǎn)說(shuō)，就是從grid[0][0] 走到`grid[m][n]的最小值（m,n表示行列數(shù)）。如果用i,j表示行列的指針，那如果可以求得走到grid[i][j]的最小值，就是題解的關(guān)鍵了，那我們就用dp[i][j]來(lái)表示走到當(dāng)前點(diǎn)的最小路徑。

那對(duì)于grid[i][j]來(lái)說(shuō)，走到當(dāng)前位置，要么從其上方，要么從其左方，要取這兩種路徑的最小值，最后再加上此點(diǎn)本身。那么 dp  方程(狀態(tài)轉(zhuǎn)移方程)就是這樣了：

dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]

上面的考慮還是有漏洞，要考慮i=0或者j=0的情況，也就是當(dāng)前點(diǎn)在左側(cè)邊上或者第一行，這種情況，上面的公式不成立，需要單獨(dú)列出來(lái)：

//在左側(cè)邊上即第1列
dp[i][0] = dp[i-1][0]+ grid[i][0];
//在第1行
dp[0][j] = dp[0][j-1]+ grid[0][j-1]

完整代碼就是這樣：

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
     if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        var r = grid.length, c = grid[0].length;
        var dp = Array.from(new Array(r),() => new Array(c));
        dp[0][0] = grid[0][0];
        for (var i = 0; i < r; i++) {
            for (var j = 0; j < c; j++) {
                // 在第一行
                if(i===0&&j!==0)
                dp[i][j] = dp[i][j - 1] + grid[i][j];
                // 在第一列
                else if(i!== 0&& j===0)
                dp[i][j] = dp[i-1][j] + grid[i][j];
                else if(i!==0&&j!==0)
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
      return dp[r - 1][c - 1];
};

動(dòng)態(tài)規(guī)劃題目的套路就是要找到你的狀態(tài)態(tài)轉(zhuǎn)移方程：dp，這個(gè)方程是動(dòng)態(tài)規(guī)劃的靈魂；還有一個(gè)要點(diǎn)是這個(gè)方程一定要有一個(gè)臨界值，而且這個(gè)值是可以直接出結(jié)果的，有了方程和一個(gè)常量臨界值，就可以依靠計(jì)算機(jī)的強(qiáng)大計(jì)算能力，遞推計(jì)算出所有情況的值，最后合并為結(jié)果。

復(fù)雜度分析

時(shí)間復(fù)雜度：O(mn)

空間復(fù)雜度：O(mn)，這個(gè)要解釋下，因?yàn)閯?chuàng)建了一個(gè)二維數(shù)組，所以復(fù)雜度是O(mn)

題目鏈接：https://leetcode-cn.com/problems/minimum-path-sum