題目

LeetCode - 746. Min Cost Climbing Stairs

解題思路

此題要求從stair[0]或stair[1]開始爬到top所需的最小cost，這題可以利用dp來解dp[i] = 爬到第i階所需的最小cost

Code

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