746. Min Cost Climbing Stairs

746. Min Cost Climbing Stairs

自頂向下

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
         
            @cache
            def dp(i):
                if i > len(cost):
                    return float('inf')
                if i == len(cost):
                    return 0
                curr = cost[i]
                return curr + min(dp(i + 1), dp(i + 2))
            
            return min(dp(0), dp(1))

自底向上

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        costs = [0] * (len(cost) + 1)
        costs[0] = cost[0]
        costs[1] = cost[1]
        cost.append(0)
        
        i = 2
        while i < len(costs):
            costs[i] = cost[i] + min(costs[i-1], costs[i-2])
            i += 1

        return costs[-1]