Problem statement

cost[i] is the fee to step on stair i; after paying you may climb 1 or 2 stairs. You start from stair 0 or stair 1.

Return the minimum cost to reach the top of the floor (just past the last stair).

Example 1

Input: cost = [10,15,20]
Output: 15
Explanation: Start at stair 1, pay 15, jump to the top.

Example 2

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

Constraints

• 2 <= cost.length <= 30
• 0 <= cost[i] <= 100

Hints for Min Cost Climbing Stairs

1. Hint 1

   minTo(i) = min(minTo(i-1) + cost[i-1], minTo(i-2) + cost[i-2]).

2. Hint 2

   Only two previous values are needed at any time.

How to solve Min Cost Climbing Stairs

Let best[i] be the cheapest way to reach stair i. You arrive either from i-1 (paying that stair's fee) or from i-2 (paying its fee), so take the smaller. The target is the floor just past the last stair, index n, which you reach from the final two stairs.

Approach

1. best[0] = best[1] = 0 — starting on either of the first two stairs is free.
2. For i from 2 to n, set best[i] = min(best[i-2] + cost[i-2], best[i-1] + cost[i-1]).
3. Note that the fee is paid when you leave a stair, which is why the cost index trails the position index by one.
4. Return best[n], and keep only the last two values to stay in constant space.

Why it works

Reaching stair i is only possible from i-1 or i-2, and those subproblems are independent of how you got to them — the future cost depends solely on where you stand. That is optimal substructure, so taking the minimum of the two options is safe at every step and the recurrence yields the global optimum.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The goal is index n, one past the last stair — stopping at n - 1 solves a different problem.
• You may start at stair 0 or stair 1, so both base cases are zero, not cost[0].
• The index offset is the trap: reaching i from i-1 costs cost[i-1], not cost[i].
• Fees can be 0, which is fine and needs no special handling.

Reference solution

Python

from typing import List

def minCostClimbingStairs(cost: List[int]) -> int:
    a, b = 0, 0
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i - 1], a + cost[i - 2])
    return b

Java

public static int minCostClimbingStairs(int[] cost) {
    int n = cost.length, a = 0, b = 0;
    for (int i = 2; i <= n; i++) {
        int c = Math.min(a + cost[i - 2], b + cost[i - 1]);
        a = b;
        b = c;
    }
    return b;
}

C++

int minCostClimbingStairs(vector<int>& cost) {
    int n = (int) cost.size(), a = 0, b = 0;
    for (int i = 2; i <= n; i++) {
        int c = min(a + cost[i - 2], b + cost[i - 1]);
        a = b;
        b = c;
    }
    return b;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy