題目描述:給定一個 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。
時間複雜度: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,不快取結果。最差情況下時間複雜度為指數級,僅適用於極小矩陣,實際不可行。