題目描述:給定一個陣列 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])
答案: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) = 30min(30, 15) = 15(只需踩第 1 階,付 15,再走兩步到頂)時間複雜度:O(n) — 單次線性掃描陣列,每個元素處理一次。
空間複雜度:O(1) — 只使用兩個滾動變數 prev1 和 prev2,不需要額外的 DP 陣列。
1. Set prev2 = cost[0], prev1 = cost[1]. 2. For i from 2 to n-1: a. curr = cost[i] + min(prev1, prev2) b. prev2 = prev1 c. prev1 = curr 3. Return min(prev1, prev2).
標準 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)),並使用哈希表快取結果。適合理解遞迴結構,但有函式呼叫開銷。
cost 陣列是動態更新的(例如某些樓梯的費用會改變),有什麼方法能高效地重新計算答案,而不需從頭掃描整個陣列?