HardRating 1965
329. Longest Increasing Path in a Matrix
arraydynamic-programmingdepth-first-searchbreadth-first-searchgraphtopological-sortmemoizationmatrix
解題說明
Longest Increasing Path in a Matrix
題目描述：給定一個 m × n 的整數矩陣 matrix，找出其中最長嚴格遞增路徑的長度。路徑可以向上、下、左、右四個方向移動，但不能斜走，也不能越出邊界。
解題思路：
DFS + 記憶化（Top-Down DP）：
對矩陣中的每個格子 (r, c)，定義 dfs(r, c) 為以該格子為起點的最長嚴格遞增路徑長度。
關鍵洞察：由於路徑要求嚴格遞增，從任一格出發只能走到值更大的相鄰格，因此圖中不存在環，DFS 天然不會回頭，不需要 visited 陣列。
轉移：
dfs(r, c) = 1 + max(dfs(nr, nc)) for all valid neighbors (nr, nc) with matrix[nr][nc] > matrix[r][c]
若無合法相鄰格，dfs(r, c) = 1（路徑只包含自身）。
記憶化：用 memo[r][c] 儲存已計算的結果，避免重複計算。
整體流程：遍歷矩陣每個格子，呼叫 dfs，取所有結果的最大值。
範例：
matrix = [[9,9,4],
[6,6,8],
[2,1,1]]
最長路徑：1 → 2 → 6 → 9，長度為 4。
C++ 解法
複雜度分析
時間複雜度：O(m × n) — 每個格子最多被計算一次（記憶化確保），每次計算檢查 4 個方向，故總時間為 O(4 × m × n) = O(m × n)。
空間複雜度：O(m × n) — 記憶化陣列 memo 大小為 m × n；遞迴深度最差為 O(m × n)（路徑遍歷所有格子），呼叫堆疊也為 O(m × n)。
虛擬碼
1. Initialize memo[m][n] = 0 (0 means unvisited).
2. Define dfs(r, c):
a. If memo[r][c] != 0, return memo[r][c].
b. Set best = 1.
c. For each direction (up, down, left, right):
- Let (nr, nc) = neighbor in that direction.
- If in bounds AND matrix[nr][nc] > matrix[r][c]:
best = max(best, 1 + dfs(nr, nc))
d. memo[r][c] = best; return best.
3. ans = 0
4. For each cell (r, c) in matrix:
ans = max(ans, dfs(r, c))
5. Return ans.其他解法
拓樸排序（BFS / Peeling）O(m × n)：將每個格子視為有向圖的節點，邊從較小值指向較大值。計算每個節點的入度（有幾個更小的相鄰格），然後進行 BFS 分層（類似拓樸排序的剝洋蔥法）：從入度為 0 的節點開始，逐層往外擴展，層數即為最長路徑長度。時間與空間複雜度同為 O(m × n)，但常數因子稍大且程式碼較複雜。
暴力 DFS（無記憶化）O(2^(m×n))：對每個格子做 DFS，不快取結果。最差情況下時間複雜度為指數級，僅適用於極小矩陣，實際不可行。
延伸思考
- 若路徑改為非嚴格遞增（允許相等的值相鄰），演算法的哪個部分需要調整？為什麼需要額外處理環的問題？
- 如何修改演算法，使其不只回傳最長路徑的長度，還能輸出完整的路徑（所有格子的座標）？
- 若矩陣非常大（例如 1000 × 1000），遞迴深度可能超過系統堆疊限制，如何將遞迴改寫為迭代版本（Bottom-Up DP）？