題目

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。
請你計算并返回達到樓梯頂部的最低花費。

一、代碼實現（動態規劃優化）

func minCostClimbingStairs(cost []int) int {n := len(cost)if n == 0 {return 0}if n == 1 {return cost[0]}prevPrev, prev := cost[0], cost[1]for i := 2; i < n; i++ {current := cost[i] + min(prev, prevPrev)prevPrev, prev = prev, current}return min(prev, prevPrev)
}func min(a, b int) int {if a < b {return a}return b
}

二、算法分析

1. 核心思路

• 滾動數組優化：僅維護前兩個狀態值
• 狀態轉移方程：dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• 邊界處理：
  • 直接處理n=0和n=1的特殊情況
  • 通過滾動變量避免O(n)空間復雜度

2. 關鍵步驟

1. 初始化狀態：prevPrev=cost[0], prev=cost[1]
2. 迭代計算：
   • 計算當前臺階的最小花費
   • 更新前兩個狀態值
3. 結果返回：取最后兩個狀態的最小值

3. 復雜度

指標	值	說明
時間復雜度	O(n)	線性遍歷整個數組
空間復雜度	O(1)	僅使用三個臨時變量

---

三、圖解示例

四、邊界條件與擴展

1. 特殊場景驗證

• 空數組：返回0（題目約束通常不存在）
• 單臺階數組：直接返回cost[0]
• 兩臺階數組：取cost[0]和cost[1]較小值
• 大數測試：n=1000時仍能高效計算

2. 擴展應用

• 建筑成本優化：規劃多層建筑的最優建造路徑
• 游戲AI尋路：動態計算移動消耗最小的路徑
• 投資決策：多階段投資的最小成本路徑選擇

3. 多語言實現

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;if (n == 1) return cost[0];int a = cost[0], b = cost[1];for (int i = 2; i < n; i++) {int c = cost[i] + Math.min(a, b);a = b;b = c;}return Math.min(a, b);}
}

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:if len(cost) == 1:return cost[0]prev_prev, prev = cost[0], cost[1]for i in range(2, len(cost)):current = cost[i] + min(prev_prev, prev)prev_prev, prev = prev, currentreturn min(prev_prev, prev)

五、總結與優化

1. 算法對比

方法	優勢	適用場景
動態規劃	最優時間復雜度	常規需求
遞歸+記憶化	代碼直觀	教學演示
矩陣快速冪	O(log n)時間復雜度	極大n值計算

2. 工程優化

• 循環展開：手動展開循環減少分支判斷
• SIMD指令：利用并行計算加速向量運算
• 預計算緩存：存儲常用值減少重復計算

3. 擴展方向

• 三維路徑規劃：考慮空間中的多層移動成本
• 隨機成本模型：處理概率性變化的動態成本
• 多目標優化：平衡時間和成本的雙重約束