📘 題目敘述
給你一個整數陣列 cost，其中 cost[i] 是爬上第 i 階樓梯的花費。
當你支付 cost[i] 後，你可以從第 i 階往上爬 1 階或 2 階。
你可以選擇從第 0 階或第 1 階開始。
請回傳到達樓梯頂端的最小花費。
條件限制
2 <= cost.length <= 10000 <= cost[i] <= 999
🧠 解題思路
這題我用 DP，把「走到某一階時的最小花費」記下來。
我定義 dp[i] 表示：
走到第 i 階（並且踩上它、付出 cost[i]）的最小花費是多少。
那要到第 i 階，只可能從：
- 第
i-1階走 1 步上來 - 第
i-2階走 2 步上來
所以遞推式就是：
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
最後題目要到的是「樓梯頂端」，頂端是在 n 的位置，不算一個真正的階梯，所以最後一步可以從：
n-1踩上去後走 1 步到頂n-2踩上去後走 2 步到頂
因此答案是：
min(dp[n-1], dp[n-2])
所有變數
n：樓梯階數（cost.size()）dp：DP 陣列，dp[i]表示踩到第i階時的最小花費i：用來從 2 推到 n-1 的迴圈索引
🪜 主要流程步驟
1. 初始化 dp[0] 與 dp[1]
因為可以從 0 或 1 開始，所以：
- 踩到第 0 階的最小花費就是
cost[0] - 踩到第 1 階的最小花費就是
cost[1]
所以我先設：
dp[0] = cost[0]dp[1] = cost[1]
2. 由小到大推 dp[i]
從 i = 2 到 n-1：
dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
3. 回傳到頂端的最小花費
到頂端不用付費，所以只要看最後一步從哪一階上去最便宜：
回傳 min(dp[n-1], dp[n-2])。
⏱️ 複雜度
- 時間複雜度：
O(n) - 空間複雜度：
O(n)
💻 程式碼實作
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n);
dp[0] = cost[0], dp[1] = cost[1];
for (int i = 2; i < n; i++) {
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
}
return min(dp[n - 1], dp[n - 2]);
}
};
🔗 題目連結
https://leetcode.com/problems/min-cost-climbing-stairs/