Description
給定一個整數陣列
cost，cost[i]是從第i階往上爬的花費。你可以從第 0 階或第 1 階開始，每次可以爬 1 或 2 階。求到達頂端的最小花費。
Example:
Input: cost = [10,15,20] Output: 15
Intuition#
到達第 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#
- 概念: 建立長度
n+1的 DP 陣列，逐步填表 - 時間複雜度:
O(n) - 空間複雜度:
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(1) - 時間複雜度:
O(n) - 空間複雜度:
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 加上成本選擇
- 關鍵技巧: 注意「頂端」是超出陣列的位置（index = n），起點可以是 0 或 1 所以
dp[0] = dp[1] = 0