LeetCode 最小路徑和：動態規劃空間優化至一維

題目描述

給定 m x n 非負整數矩陣，從左上角走到右下角，只能向右/向下，求路徑上數字和的最小值。

範例：

輸入: [[1,2,4],[2,4,1],[3,2,1]]
輸出: 9
路徑: 1→2→4→1→1 (和=9)

解題思路：一維 DP 滾動更新

狀態定義：dp[j] 表示到達當前行第 j 列的最小路徑和。

1. 初始化首行：dp[j] = dp[j-1] + grid[0][j]
2. 逐行更新：

• dp[0] += grid[i][0]（首列只能從上方來）
• dp[j] = min(dp[j], dp[j-1]) + grid[i][j]（取上/左較小）

時間複雜度：O(mn)，空間複雜度：O(n)。

Python 參考實現

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        dp = [0] * n
        dp[0] = grid[0][0]
        
        # 首行初始化
        for j in range(1, n):
            dp[j] = dp[j-1] + grid[0][j]
        
        # 逐行滾動
        for i in range(1, m):
            dp[0] += grid[i][0]  # 首列
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        
        return dp[-1]

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.minPathSum([[1,2,4],[2,4,1],[3,2,1]]) == 9
    assert sol.minPathSum([[1,3,1],[1,5,1],[4,2,1]]) == 7
    print("所有測試通過")

核心要點總結

• 狀態壓縮：二維 dp[i][j] 只依賴 dp[i-1][j]（上）和 dp[i][j-1]（左），一維數組覆蓋即可
• 首列單獨處理：dp[0] 只能從上方累加
• 原地更新順序：左→右遍歷，dp[j-1] 已是當前行左值，dp[j] 仍是上行值
• 非負保證：無負數環，DP 最優子結構成立

最小路徑和是網格 DP 空間優化的標準範例，掌握「一維滾動 + 更新順序」技巧，可應用於「最小路徑和 II/III」、「不同路徑」等同類問題。