leetcode 64. 最小路徑和（遞回 / 動態規劃解法圖解）（Java版）

題目

leetcode 64. 最小路徑和

提示：

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

題解

方法一：遞回解法（超時）

right 表示當前向已右走的步數，down 表示當前已向下走的步數，cur 表示當前走過的路徑和，

此方法超時，應該使用 （方法二）動態規劃解法，

public static int minPathSum1(int[][] grid) {
    int right = 0, down = 0;
    return getMinSum(0, right, down, grid);
}

public static int getMinSum(int cur, int right, int down, int[][] grid) {
    int m = grid.length - 1; // 行邊界
    int n = grid[0].length - 1; // 列邊界

    cur += grid[down][right];
    if (right == n && down == m) { // 到終點
        return cur;
    } else if (right == n) { // 右邊界
        return getMinSum(cur, right, down + 1, grid);
    } else if (down == m) { // 下邊界
        return getMinSum(cur, right + 1, down, grid);
    } else {
        return Math.min(getMinSum(cur, right, down + 1, grid), getMinSum(cur, right + 1, down, grid));
    }
}

方法二：動態規劃

由于路徑的方向只能是向下或向右，因此網格的第一行的每個元素只能從左上角元素開始向右移動到達，網格的第一列的每個元素只能從左上角元素開始向下移動到達，此時的路徑是唯一的，因此每個元素對應的最小路徑和即為對應的路徑上的數字總和，

對于不在第一行和第一列的元素，可以從其上方相鄰元素向下移動一步到達，或者從其左方相鄰元素向右移動一步到達，元素對應的最小路徑和等于其上方相鄰元素與其左方相鄰元素兩者對應的最小路徑和中的最小值加上當前元素的值，由于每個元素對應的最小路徑和與其相鄰元素對應的最小路徑和有關，因此可以使用動態規劃求解，

創建二維陣列 dp，與原始網格的大小相同，dp[i][j] 表示從左上角出發到 (i,j) 位置的最小路徑和，顯然，dp[0][0]=grid[0][0]，對于 dp 中的其余元素，通過以下狀態轉移方程計算元素值，

狀態轉移方程：

• 當 i>0 且 j=0 時，dp[i][0] = dp[i-1][0] + grid[i][0]，

• 當 i=0 且 j>0 時，dp[0][j] = dp[0][j-1] + grid[0][j]，

• 當 i>0 且 j>0 時，dp[i][j] = min(dp[i?1][j],dp[i][j?1]) + grid[i][j]，

最后得到 dp[m-1][n-1] 的值，即為從網格左上角到網格右下角的最小路徑和，

代碼

public static int minPathSum2(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    int rows = grid.length, columns = grid[0].length;
    int[][] dp = new int[rows][columns];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < rows; i++) { // 計算最左列的值：此時左邊是邊界
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < columns; j++) { // 計算最上行的值：此時上邊是邊界
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }
    for (int i = 1; i < rows; i++) { // 其余元素
        for (int j = 1; j < columns; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[rows - 1][columns - 1];
}

復雜度分析

• 時間復雜度：O(m*n)，其中 m 和 n 分別是網格的行數和列數，需要對整個網格遍歷一次，計算 dp 的每個元素的值，

• 空間復雜度：O(m*n)，其中 m 和 n 分別是網格的行數和列數，創建一個二維陣列 dpdp，和網格大小相同，
  注：空間復雜度可以優化，例如每次只存盤上一行的 dp 值，則可以將空間復雜度優化到 O(n)，

附：4*4矩陣的16步完整程序示例

附：完整代碼（含測驗用例）

class Solution {
    public static void main(String[] args) {
//        int[][] grid = {{1, 2, 3}, {4, 5, 6}};
        int[][] grid = {{3, 8, 6, 0, 5, 9, 9, 6, 3, 4, 0, 5, 7, 3, 9, 3}, {0, 9, 2, 5, 5, 4, 9, 1, 4, 6, 9, 5, 6, 7, 3, 2}, {8, 2, 2, 3, 3, 3, 1, 6, 9, 1, 1, 6, 6, 2, 1, 9}, {1, 3, 6, 9, 9, 5, 0, 3, 4, 9, 1, 0, 9, 6, 2, 7}, {8, 6, 2, 2, 1, 3, 0, 0, 7, 2, 7, 5, 4, 8, 4, 8}, {4, 1, 9, 5, 8, 9, 9, 2, 0, 2, 5, 1, 8, 7, 0, 9}, {6, 2, 1, 7, 8, 1, 8, 5, 5, 7, 0, 2, 5, 7, 2, 1}, {8, 1, 7, 6, 2, 8, 1, 2, 2, 6, 4, 0, 5, 4, 1, 3}, {9, 2, 1, 7, 6, 1, 4, 3, 8, 6, 5, 5, 3, 9, 7, 3}, {0, 6, 0, 2, 4, 3, 7, 6, 1, 3, 8, 6, 9, 0, 0, 8}, {4, 3, 7, 2, 4, 3, 6, 4, 0, 3, 9, 5, 3, 6, 9, 3}, {2, 1, 8, 8, 4, 5, 6, 5, 8, 7, 3, 7, 7, 5, 8, 3}, {0, 7, 6, 6, 1, 2, 0, 3, 5, 0, 8, 0, 8, 7, 4, 3}, {0, 4, 3, 4, 9, 0, 1, 9, 7, 7, 8, 6, 4, 6, 9, 5}, {6, 5, 1, 9, 9, 2, 2, 7, 4, 2, 7, 2, 2, 3, 7, 2}, {7, 1, 9, 6, 1, 2, 7, 0, 9, 6, 6, 4, 4, 5, 1, 0}, {3, 4, 9, 2, 8, 3, 1, 2, 6, 9, 7, 0, 2, 4, 2, 0}, {5, 1, 8, 8, 4, 6, 8, 5, 2, 4, 1, 6, 2, 2, 9, 7}};
        System.out.println(minPathSum1(grid));
        System.out.println(minPathSum2(grid));
    }

    /**
     * 遞回解法（超時）
     */
    public static int minPathSum1(int[][] grid) {
        int right = 0, down = 0;
        return getMinSum(0, right, down, grid);
    }

    public static int getMinSum(int cur, int right, int down, int[][] grid) {
        int m = grid.length - 1; // 行邊界
        int n = grid[0].length - 1; // 列邊界

        cur += grid[down][right];
        if (right == n && down == m) { // 到終點
            return cur;
        } else if (right == n) { // 右邊界
            return getMinSum(cur, right, down + 1, grid);
        } else if (down == m) { // 下邊界
            return getMinSum(cur, right + 1, down, grid);
        } else {
            return Math.min(getMinSum(cur, right, down + 1, grid), getMinSum(cur, right + 1, down, grid));
        }
    }

    /**
     * 動態規劃解法（推薦）
     */
    public static int minPathSum2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) { // 計算最左列的值：此時左邊是邊界
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) { // 計算最上行的值：此時上邊是邊界
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) { // 其余元素
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}