How do you approach Min Cost Climbing Stairs?

Define dp[i] as the minimum total cost to reach step i. What two steps could you have come from?

What is the time complexity of Min Cost Climbing Stairs?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Min Cost Climbing Stairs?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Min Cost Climbing Stairs

EasyAlgorithms

Description

You are given an integer array `cost` where `cost[i]` is the cost of the `i`-th step on a staircase. Once you pay the cost, you can climb either **one or two steps**. You can either start from the step with index `0`, or the step with index `1`. Return the minimum cost to reach the **top of the floor** (one past the last index).

Example 1

Input: cost = [10,15,20]

Output: 15

Explanation: Start at index 1, pay 15, climb two steps to the top.

Example 2

Input: cost = [1,100,1,1,1,100,1,1,100,1]

Output: 6

Explanation: Start at index 0 and repeatedly skip the expensive 100-cost steps: pay 1 six times.

Example 3

Input: cost = [1,2]

Output: 1

Constraints

- 2 <= cost.length <= 1000 - 0 <= cost[i] <= 999

Min Cost Climbing Stairs: approach, complexity and pitfalls

An easy dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Define dp[i] as the minimum total cost to reach step i. What two steps could you have come from?
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), with dp[0] = dp[1] = 0 since you may start on step 0 or 1 for free.
You only ever look back two entries, so two rolling variables replace the whole dp array.

The optimal approach

Show the approach: Bottom-Up DP with Two Variables

Let `dp[i]` be the cheapest way to *stand on* position `i` (where `i = n` is the top). You arrive either from `i-1` (paying `cost[i-1]`) or `i-2` (paying `cost[i-2]`), and both starting steps are free, so `dp[0] = dp[1] = 0`. Since the recurrence only references the previous two values, two rolling variables suffice.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.