70. Climbing Stairs (Easy)

Problem

You are climbing a staircase of n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example

• n = 2 → 2 (1+1, 2)
• n = 3 → 3 (1+1+1, 1+2, 2+1)

LeetCode 70 · 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).

Go

▶ Run Go ↻ 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 Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, naive recursion

f(n) = f(n-1) + f(n-2).

Python

def climb_stairs(n):
    if n <= 2:              # L1: base case
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)  # L2: two recursive calls per step

TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;                              // L1: base case
    return climbStairs(n - 1) + climbStairs(n - 2);  // L2: two recursive calls per step
}

Go

func climbStairs(n int) int {
    if n <= 2 {              // L1: base case
        return n
    }
    return climbStairs(n-1) + climbStairs(n-2)  // L2: two recursive calls per step
}

Swift

final class Solution {
    func climbStairs(_ n: Int) -> Int { n <= 2 ? n : climbStairs(n - 1) + climbStairs(n - 2) }
}

Where the time goes, line by line

Variables: n = the input integer (number of stairs).

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

Each call at depth d spawns two more calls, doubling the tree width. The total node count is the Fibonacci-tree size, which grows as $O(2ⁿ)$.

Complexity

• Time: $O(2ⁿ)$, driven by L2. Exponential, same call tree as Fibonacci.
• Space: $O(n)$ recursion stack depth.

Approach 2: Top-down with memoization

Cache results by n.

Python

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs(n):
    if n <= 2:              # L1: base case
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)  # L2: two sub-calls, result cached

TypeScript

const memo = new Map<number, number>();

function climbStairs(n: number): number {
    if (n <= 2) return n;                              // L1: base case
    if (memo.has(n)) return memo.get(n)!;
    const result = climbStairs(n - 1) + climbStairs(n - 2);  // L2: two sub-calls, cached
    memo.set(n, result);
    return result;
}

Go

var memo = map[int]int{}

func climbStairs(n int) int {
    if n <= 2 {              // L1: base case
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    result := climbStairs(n-1) + climbStairs(n-2)  // L2: two sub-calls, result cached
    memo[n] = result
    return result
}

Swift

final class Solution {
    func climbStairs(_ n: Int) -> Int { var memo = [1: 1, 2: 2]; func solve(_ x: Int) -> Int { if let value = memo[x] { return value }; let value = solve(x - 1) + solve(x - 2); memo[x] = value; return value }; return solve(n) }
}

Where the time goes, line by line

Variables: n = the input integer (number of stairs).

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

Each unique n is computed once and cached. After that, every subsequent call hits the cache in $O(1)$. The total unique states is n, so all work is $O(n)$.

Complexity

• Time: $O(n)$, driven by L2 (n unique states, each computed once).
• Space: $O(n)$ cache + recursion 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

Build the full Fibonacci sequence in a dp array, one cell per step.

Python

def climb_stairs(n):
    if n <= 2:                          # L1: base case
        return n
    dp = [0] * (n + 1)                 # L2: O(n) allocation
    dp[1], dp[2] = 1, 2                # L3: seed base cases
    for i in range(3, n + 1):          # L4: loop n-2 times
        dp[i] = dp[i - 1] + dp[i - 2] # L5: O(1) recurrence
    return dp[n]                        # L6: O(1) return

TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;                          // L1: base case
    const dp = new Array(n + 1).fill(0);           // L2: O(n) allocation
    dp[1] = 1;
    dp[2] = 2;                                     // L3: seed base cases
    for (let i = 3; i <= n; i++) {                 // L4: loop n-2 times
        dp[i] = dp[i - 1] + dp[i - 2];            // L5: O(1) recurrence
    }
    return dp[n];                                  // L6: O(1) return
}

Go

func climbStairs(n int) int {
    if n <= 2 {                              // L1: base case
        return n
    }
    dp := make([]int, n+1)                  // L2: O(n) allocation
    dp[1], dp[2] = 1, 2                     // L3: seed base cases
    for i := 3; i <= n; i++ {              // L4: loop n-2 times
        dp[i] = dp[i-1] + dp[i-2]          // L5: O(1) recurrence
    }
    return dp[n]                             // L6: O(1) return
}

Swift

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

Where the time goes, line by line

Variables: n = the input integer.

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

Complexity

• Time: $O(n)$, driven by L4/L5 (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)

Only the last two values are needed.

Python

def climb_stairs(n):
    if n <= 2:                    # L1: base case O(1)
        return n
    a, b = 1, 2                   # L2: init f(1), f(2)
    for _ in range(3, n + 1):     # L3: loop runs n-2 times
        a, b = b, a + b           # L4: O(1) update per iteration
    return b

TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;         // L1: base case O(1)
    let a = 1, b = 2;             // L2: init f(1), f(2)
    for (let i = 3; i <= n; i++) { // L3: loop runs n-2 times
        [a, b] = [b, a + b];      // L4: O(1) update per iteration
    }
    return b;
}

Go

func climbStairs(n int) int {
    if n <= 2 {                  // L1: base case O(1)
        return n
    }
    a, b := 1, 2                 // L2: init f(1), f(2)
    for i := 3; i <= n; i++ {   // L3: loop runs n-2 times
        a, b = b, a+b            // L4: O(1) update per iteration
    }
    return b
}

Swift

final class Solution {
    func climbStairs(_ n: Int) -> Int { if n <= 2 { return n }; var first = 1, second = 2; for _ in 3...n { (first, second) = (second, first + second) }; return second }
}

Where the time goes, line by line

Variables: n = the input integer (number of stairs).

Line	Per-call cost	Times executed	Contribution
L1 (base check)	$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)$

The loop runs exactly n - 2 times; each iteration is a fixed-cost swap-and-add. Nothing allocates.

Complexity

• Time: $O(n)$, driven by L3/L4 (n - 2 iterations).
• 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 recursion	$O(n)$	$O(n)$
Bottom-up, dp array	$O(n)$	$O(n)$
Bottom-up, two vars	$O(n)$	$O(1)$

Template for every Fibonacci-shape DP (House Robber, Min Cost Climbing Stairs, Tribonacci, etc.).

Test cases

Python

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

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

def _run_tests():
    assert climb_stairs(1) == 1    # single step: one way
    assert climb_stairs(2) == 2    # (1+1) or (2): two ways
    assert climb_stairs(3) == 3    # (1+1+1),(1+2),(2+1): three ways
    assert climb_stairs(4) == 5
    assert climb_stairs(5) == 8
    assert climb_stairs(10) == 89
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function climbStairs(n: number): number {
    if (n <= 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

console.assert(climbStairs(1) === 1);
console.assert(climbStairs(2) === 2);
console.assert(climbStairs(3) === 3);
console.assert(climbStairs(4) === 5);
console.assert(climbStairs(5) === 8);
console.assert(climbStairs(10) === 89);
console.log('all tests pass');

Go

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    a, b := 1, 2
    for i := 3; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

func main() {
    assert(climbStairs(1) == 1)
    assert(climbStairs(2) == 2)
    assert(climbStairs(3) == 3)
    assert(climbStairs(4) == 5)
    assert(climbStairs(5) == 8)
    assert(climbStairs(10) == 89)
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, conceptual DP array (here collapsed to two scalars)

Related concepts

• Tabulation, the bottom up table fill that solves dependencies in a reliable order.
• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.