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.

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.