746. Min Cost Climbing Stairs (Easy)

Problem

Given an array cost where cost[i] is the cost of step i, you can start at step 0 or step 1. Each move climbs 1 or 2 steps. Return the minimum total cost to reach just past the last step.

Example

• cost = [10, 15, 20] → 15 (start at 1, pay 15, step over the top)
• cost = [1,100,1,1,1,100,1,1,100,1] → 6

LeetCode 746 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive, min cost from step i

min_from(i) = cost[i] + min(min_from(i+1), min_from(i+2)). Return min(min_from(0), min_from(1)).

Python

def min_cost_climbing_stairs(cost):
    n = len(cost)
    def min_from(i):
        if i >= n:        # L1: base case, past top
            return 0
        return cost[i] + min(min_from(i + 1), min_from(i + 2))  # L2: two recursive branches
    return min(min_from(0), min_from(1))  # L3: best of starting at 0 or 1

TypeScript

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    function minFrom(i: number): number {
        if (i >= n) return 0;                                              // L1: base case, past top
        return cost[i] + Math.min(minFrom(i + 1), minFrom(i + 2));        // L2: two recursive branches
    }
    return Math.min(minFrom(0), minFrom(1));                               // L3: best of 0 or 1
}

Swift

final class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int { func solve(_ i: Int) -> Int { i >= cost.count ? 0 : cost[i] + min(solve(i + 1), solve(i + 2)) }; return min(solve(0), solve(1)) }
}

Where the time goes, line by line

Variables: n = len(cost).

Line	Per-call cost	Times executed	Contribution
L1 (base case)	$O(1)$	$O(2ⁿ)$ leaves	$O(2ⁿ)$
L2 (two recursive calls)	$O(1)$ + subtree	$O(2ⁿ)$ nodes	$O(2ⁿ)$ ← dominates
L3 (initial call)	$O(1)$	1	$O(1)$

Each call spawns two more; the tree doubles in width at every level, giving an exponential node count.

Complexity

• Time: $O(2ⁿ)$, driven by L2 (exponential branching, no caching).
• Space: $O(n)$ recursion stack.

Approach 2: Memoized recursion

Python

from functools import lru_cache

def min_cost_climbing_stairs(cost):
    n = len(cost)
    @lru_cache(maxsize=None)
    def f(i):
        if i >= n:             # L1: base case
            return 0
        return cost[i] + min(f(i + 1), f(i + 2))  # L2: two sub-calls, cached after first hit
    return min(f(0), f(1))    # L3: best start

TypeScript

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const memo = new Map<number, number>();
    function f(i: number): number {
        if (i >= n) return 0;                                          // L1: base case
        if (memo.has(i)) return memo.get(i)!;
        const result = cost[i] + Math.min(f(i + 1), f(i + 2));       // L2: two sub-calls, cached
        memo.set(i, result);
        return result;
    }
    return Math.min(f(0), f(1));                                       // L3: best start
}

Swift

final class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int { var memo: [Int: Int] = [:]; func solve(_ i: Int) -> Int { if i >= cost.count { return 0 }; if let v = memo[i] { return v }; let v = cost[i] + min(solve(i + 1), solve(i + 2)); memo[i] = v; return v }; return min(solve(0), solve(1)) }
}

Where the time goes, line by line

Variables: n = len(cost).

Line	Per-call cost	Times executed	Contribution
L1 (base case)	$O(1)$	2	$O(1)$
L2 (cached sub-calls)	$O(1)$ each	n unique states	$O(n)$ ← dominates
L3 (initial call)	$O(1)$	1	$O(1)$

Each of the n steps is computed exactly once; subsequent calls hit the cache in $O(1)$.

Complexity

• Time: $O(n)$, driven by L2 (n unique states, each computed once).
• Space: $O(n)$ cache + stack.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Bottom-up DP array

dp[i] = min cost to step on stair i. Build iteratively from left to right.

Python

def min_cost_climbing_stairs(cost):
    n = len(cost)
    dp = [0] * n                               # L1: O(n) allocation
    dp[0], dp[1] = cost[0], cost[1]            # L2: seed base cases
    for i in range(2, n):                      # L3: loop n-2 times
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])  # L4: O(1) recurrence
    return min(dp[n-1], dp[n-2])               # L5: O(1) return

TypeScript

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const dp = new Array(n).fill(0);              // L1: O(n) allocation
    dp[0] = cost[0];
    dp[1] = cost[1];                              // L2: seed base cases
    for (let i = 2; i < n; i++) {               // L3: loop n-2 times
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);  // L4: O(1) recurrence
    }
    return Math.min(dp[n - 1], dp[n - 2]);        // L5: O(1) return
}

Swift

final class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int { var dp = Array(repeating: 0, count: cost.count + 1); if cost.count >= 2 { for i in 2...cost.count { dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) } }; return dp[cost.count] }
}

Where the time goes, line by line

Variables: n = len(cost).

Line	Per-call cost	Times executed	Contribution
L1 (allocate dp)	$O(n)$	1	$O(n)$
L2 (seed)	$O(1)$	1	$O(1)$
L3, L4 (loop + recurrence)	$O(1)$	n - 2	$O(n)$ ← dominates
L5 (return)	$O(1)$	1	$O(1)$

Complexity

• Time: $O(n)$, driven by L3/L4 (n - 2 iterations).
• Space: $O(n)$ for the dp array.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 4: Bottom-up with two variables (optimal)

dp[i] = min cost to stand on step i. Then dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Answer = min(dp[n-1], dp[n-2]).

Python

def min_cost_climbing_stairs(cost):
    n = len(cost)                       # L1: get length
    a, b = cost[0], cost[1]             # L2: seed dp[0], dp[1]
    for i in range(2, n):               # L3: loop n-2 times
        a, b = b, cost[i] + min(a, b)  # L4: O(1) update per step
    return min(a, b)                    # L5: best of last two steps

TypeScript

function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;                    // L1: get length
    let a = cost[0], b = cost[1];            // L2: seed dp[0], dp[1]
    for (let i = 2; i < n; i++) {           // L3: loop n-2 times
        [a, b] = [b, cost[i] + Math.min(a, b)];  // L4: O(1) update per step
    }
    return Math.min(a, b);                   // L5: best of last two steps
}

Swift

final class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int { var twoBack = 0, oneBack = 0; for i in 2...cost.count { let current = min(oneBack + cost[i - 1], twoBack + cost[i - 2]); twoBack = oneBack; oneBack = current }; return oneBack }
}

Where the time goes, line by line

Variables: n = len(cost).

Line	Per-call cost	Times executed	Contribution
L1 (length)	$O(1)$	1	$O(1)$
L2 (init)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$	n - 2	$O(n)$ ← dominates
L4 (update)	$O(1)$	n - 2	$O(n)$
L5 (final min)	$O(1)$	1	$O(1)$

The loop runs exactly n - 2 times, each iteration is a constant-cost update. No allocation beyond two scalars.

Complexity

• Time: $O(n)$, driven by L3/L4.
• Space: $O(1)$, just two scalars.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Naive recursion	$O(2ⁿ)$	$O(n)$
Memoized	$O(n)$	$O(n)$
Bottom-up, dp array	$O(n)$	$O(n)$
Bottom-up, two vars	$O(n)$	$O(1)$

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_746.py and run.
# Uses the canonical implementation (Approach 4: bottom-up two variables).

def min_cost_climbing_stairs(cost):
    n = len(cost)
    a, b = cost[0], cost[1]
    for i in range(2, n):
        a, b = b, cost[i] + min(a, b)
    return min(a, b)

def _run_tests():
    assert min_cost_climbing_stairs([10, 15, 20]) == 15       # LeetCode example 1
    assert min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1]) == 6  # LeetCode example 2
    assert min_cost_climbing_stairs([0, 0]) == 0              # all zeros
    assert min_cost_climbing_stairs([1, 2]) == 1              # two steps, pick cheaper
    assert min_cost_climbing_stairs([5, 3, 1, 2]) == 4        # skip alternating
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

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

console.assert(minCostClimbingStairs([10, 15, 20]) === 15);
console.assert(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]) === 6);
console.assert(minCostClimbingStairs([0, 0]) === 0);
console.assert(minCostClimbingStairs([1, 2]) === 1);
console.assert(minCostClimbingStairs([5, 3, 1, 2]) === 4);
console.log('all tests pass');

Related data structures

• Arrays, input; implicit DP array

Related concepts

• State Compression, the memory reduction tactic for keeping only states the next transition needs.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.