Skip to main content

746. Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

Python​

Bottom-up DP​

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) < 3:
            return min(cost)

        dp = [0] * (len(cost)+1)

        for i in range(2, len(cost)+1):
            take_one = dp[i-1] + cost[i-1]
            take_two = dp[i-2] + cost[i-2]
            dp[i] = min(take_one, take_two)

        return dp[-1]

Top-down DP​

from functools import cache


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) < 3:
            return min(cost)

        @cache
        def dp(stair: int) -> int:
            if stair < 2:
                return 0
            down_1 = cost[stair-1] + dp(stair-1)
            down_2 = cost[stair-2] + dp(stair-2)
            return min(down_1, down_2)

        return dp(len(cost))