題目連結: 746. Min Cost Climbing Stairs

題目描述:給你一個整數陣列 cost，其中 cost[i] 是你從第 i 個台階向上爬一步需要支付的費用。一旦你付了這個費用，你可以選擇向上爬一階或兩階。
你可以選擇從索引為 0 或 1 的台階開始。
請計算並返回你到達樓頂（即越過最後一個台階）的最低費用。

Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

• Pay 15 and climb two steps to reach the top.
  The total cost is 15.

Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top.
  The total cost is 6.

Python

解題思路:
DP 的核心思想不僅可以用來計數，更常用來求解最優值。通過將狀態轉移方程中的「加法」換成「取 min 或 max」，我們就能解決一大類新的問題。

這個問題的結構與「爬樓梯」高度相似，因此我們同樣可以使用動態規劃來解決。

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp0,dp1 = 0,0
        for i in range(len(cost)):
            curr = cost[i] + min(dp0,dp1)
            dp1 = dp0
            dp0 = curr
        return min(dp1,dp0)

演算法分析:

• 我們可以想像在 cost 陣列開始前有第 -1 階和第 -2 階，成本都為 0。
• 計算到達當前台階 i 之後的位置（即 i+1）的最小成本，它可從i-1 或 i-2 走過來，min(從 i-2 過來的成本, 從 i-1 過來的成本)。
• 遍歷結束後，dp1 和 dp0 分別代表到達最後兩階的最小成本。
• 樓頂可以從最後一階或倒數第二階到達，取其較小值。

複雜度分析:

• 時間複雜度為 O(n)(我們只需要一個 for 迴圈遍歷一次 cost 陣列。)。
• 空間複雜度： O(1)(我們只使用了 dp0, dp1, curr 等固定數量的變數。)。

有問題可以底下留言!
下回見!!