Code Logo

Min Cost Climbing Stairs

Published at24 Jul 2026
Created by
Easy 0 views
Like0

You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. You can either start at step 0 or step 1. Once you pay the cost, you can climb either one or two steps. Find the minimum cost to reach the top of the floor beyond the last step.

This is a classic DP problem where the minimum cost to reach step i is the cost of step i plus the minimum of the costs to reach either of the two previous steps: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). The answer is the minimum of the costs to reach the last two steps, because you can finish by taking either one or two steps from the top.

The base cases are the first two steps: dp[0] = cost[0] and dp[1] = cost[1]. The recurrence builds up to the top. Space optimization uses two variables instead of an array, as each step only depends on the two previous values.

Edge cases include cost array of length 2 (return min of both), all zero costs (return 0), and increasing costs that make the greedy choice suboptimal — the DP solution always finds the optimal minimum.

The min cost problem differs from the basic climbing stairs because costs are associated with each step rather than counting ways. The DP recurrence captures the optimal substructure: the cheapest way to reach step i depends only on the cheapest ways to reach the two preceding steps.

Example Input & Output

Example 1
Input
[10,15,20]
Output
15
Explanation

Start at step 0 (pay 10), climb 2 to step 2 (pay 20), climb 1 to top. Total=15 from step 1.

Example 2
Input
[5,10]
Output
5
Explanation

Start at step 0, pay 5, climb to top.

Example 3
Input
[1,2,3,4]
Output
4
Explanation

Path: step 1 (pay 2), step 3 (pay 4) → or step 0 (pay 1), step 2 (pay 3) → min is 4.

Example 4
Input
[1,100,1,1,1,100,1,1,100,1]
Output
6
Explanation

Optimal path: pay 1s at indices 0,2,3,5,6,8... total 6.

Example 5
Input
[0,0,0,0]
Output
0
Explanation

All zero, no cost.

Algorithm Flow

Recommendation Algorithm Flow for Min Cost Climbing Stairs
Recommendation Algorithm Flow for Min Cost Climbing Stairs

Solution Approach

DP: dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Return min of last two dp values.

function solution(cost) {
  var a = cost[0], b = cost[1];
  for (var i = 2; i < cost.length; i++) {
    var c = cost[i] + Math.min(a, b);
    a = b;
    b = c;
  }
  return Math.min(a, b);
}

Time O(n), Space O(1).

Best Answers

java
class Solution {
    public int solution(int[] cost) {
        int a = cost[0], b = cost[1];
        for (int i = 2; i < cost.length; i++) {
            int c = cost[i] + Math.min(a, b);
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}