題目描述

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

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

示例：

輸入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。

暴力遞歸思路

1.我們可以將每個(gè)位置向右和向下的結(jié)果都求出來(lái)，然后每次都選擇最小的加起來(lái)即可。

Java代碼實(shí)現(xiàn)

    public int minPathSum(int[][] grid) {
        return minPathSum(grid,0,0);
    }

    private int minPathSum(int[][] grid,int i,int j,int[][] memory) {
        if(i == grid.length)
            return Integer.MAX_VALUE-grid[i-1][j];
        if(j == grid[0].length)
            return Integer.MAX_VALUE-grid[i][j-1];
        if(i == grid.length-1 && j == grid[0].length-1)
            return grid[i][j];
        int path1 = grid[i][j]+minPathSum(grid,i+1,j,memory);
        int path2 = grid[i][j]+minPathSum(grid,i,j+1,memory);
        int curPath = Math.min(path1,path2);
        return curPath;
    }

備忘錄方法

1.我們可以發(fā)現(xiàn)暴力法會(huì)將同一個(gè)位置的答案計(jì)算多次，所以我們可以將計(jì)算過(guò)的答案存儲(chǔ)起來(lái)，如果發(fā)現(xiàn)該位置的答案已經(jīng)算好了，就不用再遞歸求結(jié)果了，可以大幅度減少遞歸的次數(shù)。

Java代碼實(shí)現(xiàn)

    public int minPathSum(int[][] grid) {
        int[][] memory = new int[grid.length][grid[0].length];
        return minPathSum(grid,0,0,memory);
    }

    private int minPathSum(int[][] grid,int i,int j,int[][] memory) {
        if(i == grid.length)
            return Integer.MAX_VALUE-grid[i-1][j];
        if(j == grid[0].length)
            return Integer.MAX_VALUE-grid[i][j-1];
        if(i == grid.length-1 && j == grid[0].length-1)
            return grid[i][j];
        if(memory[i][j] != 0)
            return memory[i][j];
        int path1 = grid[i][j]+minPathSum(grid,i+1,j,memory);
        int path2 = grid[i][j]+minPathSum(grid,i,j+1,memory);
        int curPath = Math.min(path1,path2);
        memory[i][j] = curPath;
        return curPath;
    }

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

1.我們可以通過(guò)以上兩種方法可以總結(jié)出狀態(tài)轉(zhuǎn)移方程為：dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1))
2.我們?cè)O(shè)置一個(gè)二維數(shù)組存儲(chǔ)dp的結(jié)果，然后將dp[0][0]作為結(jié)果返回即可。

Java代碼實(shí)現(xiàn)

    public int minPathSum(int[][] grid) {
        int[][] res = new int[grid.length+1][grid[0].length+1];
        for (int i = grid.length-1; i >= 0 ; i--) {
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (i == grid.length - 1 && j == grid[0].length - 1) {
                    res[i][j] = grid[i][j];
                    continue;
                }
                //如果是最后一行
                if (i == grid.length - 1) {
                    res[i][j] = grid[i][j] + res[i][j + 1];
                    continue;
                }
                //如果是最后一列
                if (j == grid[0].length - 1) {
                    res[i][j] = grid[i][j] + res[i + 1][j];
                    continue;
                }
                res[i][j] = Math.min(grid[i][j] + res[i][j + 1], grid[i][j] + res[i + 1][j]);
            }
        }
        return res[0][0];
    }