題目出處

746. Min Cost Climbing Stairs

難度

Easy

個人範例程式碼

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0

        dp = []

        for i in range(len(cost)+1):
            if i <= 1:
                dp.append(0)
            else:
                dp.append(min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]))

        return dp[-1]

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

算是陽春的 DP 問題，

• 主要目標：dp[i] = min(dp[i-2]+A[i-2], dp[i-1]+A[i-1])
• 初始目標:
  • dp[0] = 0
  • dp[1] = 0

最後記得要「多算一個欄位」，代表 「 top 」。

input handling

如果沒有任何 cost，return 0

Boundary conditions

for 來控制範圍

Reference

• 最少费用的爬台阶方法 · Min Cost Climbing Stairs