Leetcode : MinimumPathSum

類型：動態(tài)規(guī)劃

題目

給一個 MxN的數(shù)組矩陣，矩陣上每一個左表代表該點的路徑長度，求從左上角到右下角路徑的最短的和。
舉栗：

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output : 7 (因為最短路徑是1-3-1-1-1)

思路

解法可以有兩種，動態(tài)規(guī)劃 和 回溯法。
回溯法在這個問題下時間復(fù)雜度太高，是指數(shù)級。
動態(tài)規(guī)劃的時間復(fù)雜度是 O(MxN) M和N是矩陣的長和寬

解法

動態(tài)規(guī)劃

思路：
令矩陣中[0][0] 到 [x][y] 點的最短路徑為 minPath(x,y)
則可以得到遞推公式：
minPath(x,y) = Math.min(minPath(x-1,y), minPath(x,y-1)) + grid[x][y]

則從(0,0)到矩陣上任意一點的最短路徑都可以求得，最終的minPath(m-1,n-1) 就是我們要求的結(jié)果

leetcode submit beats 99.4% - 5ms
下面上代碼：

public static int minPathSum_DP(int[][] grid) {
        int width = grid[0].length;
        int height = grid.length;
        int[][] minDp = new int[height][width];
        int minUp, minLeft;
        for(int i=0; i<height; i++){
            for(int j=0; j<width; j++){
                if(i==0 && j==0){
                    minDp[i][j] = grid[i][j];
                    continue;
                }else if(i==0){
                    minDp[i][j] = minDp[i][j-1] + grid[i][j];
                    continue;
                }else if(j==0){
                    minDp[i][j] = minDp[i-1][j] + grid[i][j];
                    continue;
                }
                minLeft = minDp[i][j-1];
                minUp = minDp[i-1][j];
                minDp[i][j] = minLeft < minUp ? minLeft + grid[i][j] : minUp + grid[i][j];
            }
        }

        return minDp[height-1][width-1];
    }

回溯法
當(dāng)然另一個思路是使用回溯法，但是回溯法執(zhí)行時間太長，時間復(fù)雜度是指數(shù)級的。不過可以作為練習(xí)回溯法的一個TestCase

回溯法的思路是把解題的方式當(dāng)做對一個樹的深度優(yōu)先遍歷
該問題下可以進(jìn)一步優(yōu)化，在每一次往深了走的時候都校驗一下是否已經(jīng)超過目前已知最短路徑，超過就直接返回，不在計算。

代碼如下：

    static int minPath =0;
    static int width=0;
    static int height=0;
    public static int minPathSum_BC(int[][] grid) {
        width = grid[0].length;
        height = grid.length;
        backTracing(0,0,0,grid);
        return minPath;
    }

    // 回溯法要注意，由于在一個邊到頂以后還要回溯另一個邊
    // 所以數(shù)組的臨界條件不能越界, 也就是如下 w==width-1 && h==height-1
    // 相應(yīng)的，遞歸的臨界條件也應(yīng)該使得下一層不能越界
    static void backTracing(int tmp, int h, int w, int[][] grid){
        tmp += grid[h][w];
        if(minPath !=0 && tmp >= minPath){
            return;
        }

        if(h==height-1 && w==width-1){
            minPath = minPath == 0 ? tmp : (tmp<minPath ? tmp : minPath);
            return;
        }

        if(h < height-1){    // 遞歸下一層不能越界
            backTracing(tmp, h+1, w, grid);
        }
        if(w < width-1){   // 遞歸下一層不能越界
            backTracing(tmp, h, w+1, grid);
        }
    }