LeetCode 63 Minimum Path Sum：動態規劃求網格最小路徑和

題目描述

給定一個 m x n 的非負整數網格，從左上角 (0,0) 出發，每次只能向右或向下移動，求到達右下角 (m-1, n-1) 的路徑中，數字總和最小值。

動態規劃思路

定義 dp[i][j] 為從起點到 (i,j) 的最小路徑和。狀態轉移方程：

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

邊界條件：第一行只能從左邊來，第一列只能從上邊來。可直接在原數組上修改以節省空間，時間複雜度 O(mn)，空間複雜度 O(1)（原地修改）。

Java 參考實現

public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 初始化第一列
        for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
        // 初始化第一行
        for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
        // 填充其餘
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
            }
        }
        return grid[m-1][n-1];
    }
}

關鍵點總結

• 原地修改 grid 避免額外空間
• 先處理邊界行/列，再雙層迴圈填充內部
• 注意 m, n 可能為 1 的邊界情況，代碼天然兼容