Skip to main content

746. Min Cost Climbing Stairs

easy

Given a staircase where stepping on index i costs cost[i], find the minimum cost to reach the top. You can start from index 0 or 1 and step 1 or 2 stairs at a time.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb 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.

Constraints

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

Examples

Example 1

Input
cost = [10,15,20]
Output
15

Explanation: You will start at index 1. Pay 15 and climb two steps to reach the top. The total cost is 15.

Example 2

Input
cost = [1,100,1,1,1,100,1,1,100,1]
Output
6

Explanation: You will start at index 0. Pay 1 and climb two steps to reach index 2. Pay 1 and climb two steps to reach index 4. Pay 1 and climb two steps to reach index 6. Pay 1 and climb one step to reach index 7. Pay 1 and climb two steps to reach index 9. Pay 1 and climb one step to reach the top. The total cost is 6.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Let dp[i] = min cost to reach step i. The recurrence has two choices: arrive from i-1 or i-2.

Hint 2

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). Base cases: dp[0] = dp[1] = 0 since you can start at either.

Hint 3

Only the previous two dp values matter. Collapse to two scalars for O(1) space.

Solution approach

Reveal approach

Define dp[i] as the minimum cost to reach the top from step i — or equivalently, the minimum cost to land on step i. The recurrence is dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), because to land on step i you either paid cost[i-1] and took a single step from i-1, or paid cost[i-2] and jumped two from i-2. Base cases dp[0] = dp[1] = 0 (you can start at either for free). Iterate i from 2 through n inclusive and return dp[n]. Only two previous values matter, so collapse the dp array to two rolling variables.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • fibonacci

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Min Cost Climbing Stairs and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →