Grid DP網格路徑

01為什麼需要它

看到這些關鍵字就想到它：網格、只能往右或往下（移動方向不會繞回來）、路徑數、最小路徑和、障礙格、每一格只依賴上面和左邊、滾動一列省空間。

02核心概念

當網格上只能往右或往下移動，路徑永遠不會繞回走過的格子，整張網格就是一張有向無環圖，而「逐列由上到下、每列由左到右」正好是它的一個拓撲順序。定義 dp[r][c] 為「從左上角走到 (r, c)」的答案，填到 (r, c) 時，它唯一可能的兩個來源，上面 (r−1, c) 與左邊 (r, c−1)，都已經算好。

轉移式只看最後一步從哪裡來。計數（Unique Paths）：走進 (r, c) 的路，最後一步不是從上面就是從左邊，兩類互不重疊又涵蓋全部，所以 dp[r][c] = dp[r−1][c] + dp[r][c−1]，這是加法原理；障礙格沒有任何路能停在上面，設為 0。最小成本（Minimum Path Sum）：最便宜的路徑在最後一步之前的那一段，也必須是到那一格最便宜的路徑，否則換成更便宜的就能更好，所以 dp[r][c] = min(dp[r−1][c], dp[r][c−1]) + grid[r][c]。第一列只能從左邊來、第一行只能從上面來，要單獨處理。

複雜度是每格 O(1)，O(mn) 時間。每一列只依賴上一列，所以可以只留一列：由左到右掃，更新 dp[c] 之前它還是上一列的值（上面），dp[c−1] 則已經是這一列的新值（左邊），空間降到 O(n)，如果行比列多可以轉 90 度，用較短的那一邊。要還原路徑就得保留整張表，從終點往回每次走向較小的來源。沒有障礙時 Unique Paths 有公式 C(m+n−2, m−1)，這張表其實就是轉了 45 度的巴斯卡三角形；但一有障礙，公式就失效，DP 照樣成立。

常見的坑：允許往上或往左之後路徑會繞圈，網格不再是 DAG，「最小路徑」就變成最短路徑問題，要用 BFS 或 Dijkstra（Grid as Graph 那篇）；滾動一列時掃描方向必須由左到右，否則 dp[c−1] 還是舊值；起點本身是障礙時答案是 0；路徑數成長很快，20×20 就超過 32 位元。變形：只能從下一列三個相鄰格走來就是接縫裁切與 Minimum Falling Path Sum；Dungeon Game 要求「沿途生命值不能掉到 0」，得從終點反著填；兩個人同時走（Cherry Pickup）則要把兩人的位置一起放進狀態。

03演算法步驟

1. 1確認移動方向不會繞回來（只能右、下，或只能從上一列來），於是逐列由左到右填就是合法順序。
2. 2定義 dp[r][c] 為走到 (r, c) 的答案；起點 dp[0][0] 設為 1（計數）或 grid[0][0]（成本）。
3. 3第一列只看左邊、第一行只看上面；其他格計數用 上 + 左，最小成本用 min(上, 左) + grid[r][c]，障礙格設 0 或 ∞。
4. 4答案在 dp[m−1][n−1]。要路徑就從終點往回，每次走向 dp 值較小的來源，最後反轉。
5. 5只要答案時滾動一列：dp[c] = f(dp[c], dp[c−1])，更新前的 dp[c] 是上面、dp[c−1] 是左邊。

04互動示範

同一張 4×4 網格，兩種模式。「Min Path Sum」：格子右下角的小字是走進這一格的成本，藍色是正在填的格子，黃色是它選用的來源，也就是上面與左邊較小的那一個；填完後綠色標出從終點往回找到的最便宜路徑，總成本 9。「Unique Paths」：黃色同時標出上面和左邊兩格，因為兩邊的路數要相加，邊上的格子都是 1，右下角是 20，正好等於 C(6, 3)。

05程式碼

Python 放滾動一列的路徑計數（可加障礙）、保留整張表並還原路徑的最小路徑和，以及每列從三格轉移而來的接縫裁切。C++ 放 LeetCode 63 與 64 的一維寫法，並用 20×20 的空網格驗證答案確實是 C(38, 19)，需要 64 位元整數。

def unique_paths(m, n, blocked=frozenset()):
    """m×n 網格從左上走到右下、只能往右或往下的路徑數；blocked 是障礙格"""
    dp = [0] * n                     # 只留一列：更新前 dp[c] 是上面，dp[c-1] 已經是左邊
    dp[0] = 1
    for r in range(m):
        for c in range(n):
            if (r, c) in blocked:
                dp[c] = 0                # 障礙格走不到
            elif c > 0:
                dp[c] += dp[c - 1]       # 上面的路數 + 左邊的路數
    return dp[-1]


def min_path_sum(grid):
    """回傳 (最小成本, 路徑)。要還原路徑，所以保留整張表"""
    R, C = len(grid), len(grid[0])
    dp = [[0] * C for _ in range(R)]
    for r in range(R):
        for c in range(C):
            if r == 0 and c == 0:
                best = 0
            elif r == 0:
                best = dp[r][c - 1]      # 第一列只能從左邊來
            elif c == 0:
                best = dp[r - 1][c]      # 第一行只能從上面來
            else:
                best = min(dp[r - 1][c], dp[r][c - 1])
            dp[r][c] = best + grid[r][c]
    path, r, c = [], R - 1, C - 1
    while (r, c) != (0, 0):              # 從終點往回選較小的來源
        path.append((r, c))
        if c == 0 or (r > 0 and dp[r - 1][c] <= dp[r][c - 1]):
            r -= 1
        else:
            c -= 1
    return dp[-1][-1], [(0, 0)] + path[::-1]


def min_seam(energy):
    """影像接縫：每列選一個像素，下一列只能選正下方或左右斜下方，總能量最小"""
    prev = energy[0][:]
    for row in energy[1:]:
        prev = [row[c] + min(prev[max(c - 1, 0):c + 2]) for c in range(len(row))]
    return min(prev)


if __name__ == "__main__":
    print(unique_paths(4, 4), unique_paths(3, 3, {(1, 1)}), unique_paths(20, 20))   # 20 2 35345263800
    grid = [[1, 3, 1, 2], [1, 5, 1, 3], [4, 2, 1, 1], [2, 1, 3, 1]]   # 和互動示範同一張
    print(min_path_sum(grid))
    # (9, [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (3, 3)])
    print(min_seam([[3, 1, 4, 2], [5, 9, 2, 6], [5, 3, 5, 8], [9, 7, 1, 3]]))   # 7（1 → 2 → 3 → 1）

06練習題

• LeetCode 62Unique Paths（先寫二維表，再改成一列）Medium
• LeetCode 63Unique Paths II（障礙格歸零）Medium
• LeetCode 64Minimum Path SumMedium
• LeetCode 931Minimum Falling Path Sum（從上一列的三格轉移，就是接縫裁切）Medium
• LeetCode 221Maximal Square（dp 是以這格為右下角的最大正方形邊長）Medium
• LeetCode 174Dungeon Game（從終點反著填）Hard