LeetCode 筆記 - 746. Min Cost Climbing Stairs

Posted on 標籤
解析「使用最小花費爬樓梯」問題。本文展示動態規劃（DP）的基礎應用，透過從過去兩階中挑選成本較小的路徑來累加當前花費。這種逐步推導全域最優解的方式，非常適合初學者鞏固對 DP 狀態轉移與查表法的理解。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 746. Min Cost Climbing Stairs

給定一系列爬樓梯的成本，你可以選擇一次爬一階或兩階
請給出爬完的最低成本

解題思維

這題就是 Dynamic programming 的基本應用

從過去兩階挑選成本最小的階梯即可

程式碼

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        
        if (size := len(cost)) == 2:
            return min(cost)
        
        for i in range(2, size):
            cost[i] += min(cost[i - 2], cost[i - 1])
            
        return min(cost[-1], cost[-2])

也許你也會想看看