給定一個整數陣列
cost，cost[i]是從第i階往上爬的花費。你可以從第 0 階或第 1 階開始，每次可以爬 1 或 2 階。求到達頂端的最小花費。
Example:
Input: cost = [10,15,20] Output: 15
Intuition
TIP
到達第 i 階的最小花費 = min(從 i-1 來, 從 i-2 來)，選較便宜的路徑。
- 頂端是
cost.size（超過陣列最後一個元素） dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])- 同樣只依賴前兩個狀態，可用滾動變數
Approaches
1. Bottom-Up DP Array — O(n) / O(n)
- Idea: 建立長度
n+1的 DP 陣列，逐步填表 - Time:
O(n) - Space:
O(n)
class Solution {
fun minCostClimbingStairs(cost: IntArray): Int {
val n = cost.size
val dp = IntArray(n + 1)
for (i in 2..n) {
dp[i] = minOf(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
}
return dp[n]
}
}⭐ 2. Rolling Variables — O(n) / O(1)
- Idea: 只保留前兩個狀態，空間壓縮到
O(1) - Time:
O(n) - Space:
O(1)
class Solution {
fun minCostClimbingStairs(cost: IntArray): Int {
var prev2 = 0
var prev1 = 0
for (i in 2..cost.size) {
val cur = minOf(prev1 + cost[i - 1], prev2 + cost[i - 2])
prev2 = prev1
prev1 = cur
}
return prev1
}
}🔑 Takeaways
- Pattern: 帶權重的樓梯問題 — 線性 DP 加上成本選擇
- Key trick: 注意「頂端」是超出陣列的位置（index = n），起點可以是 0 或 1 所以
dp[0] = dp[1] = 0