題目描述:給定三角形陣列(第 i 層有 i+1 個數),找從頂到底的最小路徑和。每步只能移動到下一層的相鄰數(即同索引或索引+1)。
解題思路:由下而上 DP:從最後一層開始,對每個位置計算「從此位置到底的最小路徑和」。狀態轉移:dp[j] = triangle[i][j] + min(dp[j], dp[j+1])。從下往上推,最終 dp[0] 即為答案。可原地修改最後一行作為 DP 陣列,空間 O(n)。
時間複雜度:O(n²) — 共 n 層,每層最多 n 個元素。
空間複雜度:O(n) — 只保留一行 DP 陣列,長度為最底層長度 n。
1. dp = copy of triangle's last row
2. For i from n-2 down to 0:
For j from 0 to i:
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
3. Return dp[0]由上而下 DP O(n²):dp[i][j] = 從頂到 (i,j) 的最小路徑和;最後取最底層最小值 — 需要 O(n²) 空間或滾動陣列優化。
記憶化遞迴 O(n²):dfs(row, col) 回傳從 (row,col) 到底的最小和,用 memo 表避免重複計算 — 與 DP 等效但有函式呼叫開銷。