746. Min Cost Climbing Stairs

Min Cost Climbing Stairs（746）

題目描述：給定一個陣列 cost，其中 cost[i] 是踩上第 i 階樓梯所需的費用。踩上之後可以選擇走一步或兩步。你可以從第 0 階或第 1 階出發（不需付費）。求抵達「頂部」（即 cost 陣列末尾之後）的最低總費用。

解題思路：這是一道經典的一維動態規劃題目。

DP 定義：dp[i] = 「踩上第 i 階樓梯並從此出發」所需的最低費用，其值為 cost[i]（踩上的費用）加上「抵達第 i 階」的最低花費。

轉移方程：dp[i] = cost[i] + min(dp[i-1], dp[i-2])

• 到達第 i 階可以從第 i-1 階走一步，或從第 i-2 階走兩步，取兩者中代價較小的。

答案：min(dp[n-1], dp[n-2])，因為從任一最後兩階都可以直接跨越到頂部。

空間優化：只需保留前兩個狀態，可用兩個變數滾動更新，將空間複雜度壓縮至 O(1)。

範例：cost = [10, 15, 20]

• dp[0] = 10，dp[1] = 15，dp[2] = 20 + min(15, 10) = 30
• 答案 = min(30, 15) = 15（只需踩第 1 階，付 15，再走兩步到頂）

時間複雜度：O(n) — 單次線性掃描陣列，每個元素處理一次。

空間複雜度：O(1) — 只使用兩個滾動變數 prev1 和 prev2，不需要額外的 DP 陣列。

標準 DP 陣列 O(n) 時間，O(n) 空間：建立長度為 n 的 dp 陣列，dp[i] = cost[i] + min(dp[i-1], dp[i-2])，最後回傳 min(dp[n-1], dp[n-2])。邏輯相同但使用完整陣列，便於偵錯或追蹤路徑，空間換取可讀性。

遞迴 + Memoization O(n) 時間，O(n) 空間：定義 memo(i) = 從第 i 階出發的最低費用，遞迴求解 cost[i] + min(memo(i-1), memo(i-2))，並使用哈希表快取結果。適合理解遞迴結構，但有函式呼叫開銷。

1. 若每步可走 1、2 或 3 階，DP 的轉移方程該如何修改？空間優化後需要保留幾個變數？
2. 如何追蹤並輸出費用最低的具體路徑（即踩哪幾階）？
3. 若 cost 陣列是動態更新的（例如某些樓梯的費用會改變），有什麼方法能高效地重新計算答案，而不需從頭掃描整個陣列？