Min cost climbing stairs

Find the minimum cost to reach the top of a staircase given per-step costs.

dynamic programming memoization array

You are given a list of non-negative integers `cost` where `cost[i]` is the cost of stepping on the i-th stair. You start at index 0 or 1 (you may choose), and you can climb either 1 or 2 steps at a time. When you step on a stair, you pay its cost. The top is one step beyond the last index, and stepping onto the top is free. Write a function `min_cost_climbing_stairs(cost)` that returns the minimum total cost to reach the top.

Note: You must not pay any cost for the ground before the first stair. The length of `cost` is at least 2.

Constraints

`2 <= len(cost) <= 1000`
`0 <= cost[i] <= 999`

Example

>>> min_cost_climbing_stairs([10, 15, 20])
15
>>> min_cost_climbing_stairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])
6

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the minimum cost to reach stair i as depending only on the two previous stairs.

You can start on stair 0 or 1; you pay the cost of the stair you start on.

The answer is the minimum of the costs to reach the last two stairs, because the top is free.

You can use a DP array of the same length as cost, or two variables to save space.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.