Easy

Min Cost Climbing Stairs

012

Given the cost of each stair, return the minimum cost to reach the top. You may climb one or two steps at a time.

EXAMPLES

Example 1

Input
{
  "cost": [
    10,
    15,
    20
  ]
}

Output
15

FUNCTION SHAPE

cost: intArray→int

SOLUTION NOTE

dp(i) = min cost to reach top starting from step i. We must pay cost[i], then choose cheaper of next 1 or 2 steps.

Reveal reference solution +

pythonREFERENCE

def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    @cache
    def dp(i):
        if i >= n: return 0
        return cost[i] + min(dp(i+1), dp(i+2))
    return min(dp(0), dp(1))

TimeO(n)

SpaceO(n)

Open on LeetCode ↗