Climbing Stairs

A staircase has n steps. Each move climbs either 1 or 2 steps. Count the distinct ways to reach the top; the order of moves matters.

LeetCode: 70. Climbing Stairs

Example

n = 3  ->  3   (1+1+1, 1+2, 2+1)
n = 5  ->  8

Dynamic programming solves a problem by combining answers to smaller versions of the same problem, and computes each smaller answer only once. It applies when the subproblems overlap: the same subproblem is needed many times. This problem is the simplest example, and every problem in this section follows the same steps: write the recursion, notice the repeated work, and store the answers.

Brute force: recursion

The last move onto step n was either a 1-step from n - 1 or a 2-step from n - 2. So:

ways(n) = ways(n - 1) + ways(n - 2),    ways(0) = 1, ways(1) = 1

public class Main {
    static long ways(int n) {
        return n <= 1 ? 1 : ways(n - 1) + ways(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(ways(3) + " " + ways(5) + " " + ways(30));
    }
}

3 8 1346269

Time: O(2ⁿ), roughly 1.6ⁿ: ways(n - 2) is computed inside ways(n - 1) and again directly, and the duplication compounds at every level. Space: O(n) for the recursion.

graph TB
    a["ways(5)"] --> b["ways(4)"]
    a --> c["ways(3)"]
    b --> d["ways(3)"]
    b --> e["ways(2)"]
    c --> f["ways(2)"]
    c --> g["ways(1)"]

ways(3) and ways(2) already appear twice after two levels.

Optimal: compute each value once

Memoization (top-down) keeps the recursion but stores each result the first time it's computed:

A long[] array is the memo table. A stored 0 means "not computed yet", because every real answer is at least 1. Recursion depth is n, which is fine for small n.

public class Main {
    static long ways(int n, long[] memo) {
        if (n <= 1) return 1;
        if (memo[n] != 0) return memo[n];
        memo[n] = ways(n - 1, memo) + ways(n - 2, memo);
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 50;
        System.out.println(ways(n, new long[n + 1]));
    }
}

20365011074

Tabulation (bottom-up) computes the values in increasing order instead. Each value needs only the previous two, so two variables replace the table:

public class Main {
    static long ways(int n) {
        long prev = 1, cur = 1; // ways(0), ways(1)
        for (int i = 1; i < n; i++) {
            long next = prev + cur;
            prev = cur;
            cur = next;
        }
        return cur;
    }

    public static void main(String[] args) {
        System.out.println(ways(3) + " " + ways(5) + " " + ways(50) + " " + ways(0));
    }
}

3 8 20365011074 1

Time: O(n). Space: O(1) for the loop, O(n) for the memoized version.

The sequence 1, 1, 2, 3, 5, 8, ... is the Fibonacci sequence.

Edge cases

• n = 0: one way, doing nothing.
• Overflow: the count grows like 1.6ⁿ, so long overflows silently above n = 91: the value wraps to a wrong number and no exception is thrown. Use BigInteger, a modulus if the problem gives one, or Math.addExact to fail loudly.
• Steps of other sizes (for example 1, 2, or 3): ways(n) is the sum of ways(n - s) over the allowed step sizes s.