---

動態規劃解最小花費爬樓梯問題：LeetCode 746. 使用最小花費爬樓梯

---

1. 題目鏈接

LeetCode 746. 使用最小花費爬樓梯
題目要求：給定一個整數數組 cost，其中 cost[i] 是從樓梯第 i 階向上爬所需支付的費用。你可以從下標 0 或 1 的臺階開始爬，每次爬1或2階，計算達到樓梯頂部（數組末尾之后）的最小花費。

---

2. 題目描述

• 輸入：整數數組 cost，例如 [10, 15, 20]。
• 輸出：最小花費，例如 15（從下標1開始，直接走兩步到達頂部）。
• 約束條件：
  • 2 ≤ cost.length ≤ 1000
  • 0 ≤ cost[i] ≤ 999

---

3. 示例分析

示例 1：
輸入：cost = [10, 15, 20]
輸出：15
解釋：

• 從下標1開始，支付15，走兩步直接到達頂部，總花費為15。

示例 2：
輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出：6
解釋：

• 路徑為 0→2→4→6→7→9→頂部，總花費為 1+1+1+1+1+1=6。

---

4. 算法思路

動態規劃遞推

1. 狀態定義：

   • dp[i] 表示到達第 i 階的最小累計花費。
   • 注意：頂部位于第 n 階（n = cost.size()），因此需要計算 dp[n]。

2. 狀態轉移方程：

   • 到達第 i 階的最小花費由前兩階的花費決定：
     dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
   • 解釋：可以從第 i-1 階走1步，或從第 i-2 階走2步到達第 i 階。

3. 初始條件：

   • dp[0] = 0（從起點開始，無需站在下標0的臺階）。
   • dp[1] = 0（從起點開始，直接選擇下標1的臺階，無需支付下標1的費用）。

---

5. 邊界條件與注意事項

1. 邊界處理：

   • 當 cost 數組長度為 1 時，直接返回 0（無需支付任何費用即可到達頂部）。
   • 當長度為 2 時，返回 min(cost[0], cost[1])。

2. 時間復雜度：O(n)，只需遍歷一次數組。

3. 空間優化：可進一步優化為滾動變量，將空間復雜度從 O(n) 降至 O(1)。

---

6. 代碼實現與解析

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();if (n == 0) return 0;    // 處理空數組（題目約束n≥2，實際無需）if (n == 1) return 0;     // 關鍵修正：避免越界vector<int> dp(n + 1, 0); // dp[i]表示到達第i階的最小花費for (int i = 2; i <= n; i++) {dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);}return dp[n];}
};

代碼解析

1. 初始化處理：
   • 直接處理 n=0 和 n=1 的情況，避免越界錯誤。
2. 動態規劃數組：
   • dp[0] 和 dp[1] 初始化為 0，因為從起點可以選擇直接站在下標0或1的位置。
3. 遞推計算：
   • 從 i=2 開始，計算到達每階的最小花費，確保每次取最小值。
4. 返回值：
   • dp[n] 表示到達頂部（第 n 階之后）的最小花費。

---

總結

通過動態規劃遞推能夠高效解決最小花費爬樓梯問題。關鍵點在于正確處理邊界條件（如 n=1）和狀態轉移邏輯。此方法可擴展至類似路徑選擇問題，如帶權重的跳躍游戲等。