☕ DSA Java Articles

Topics › Dynamic Programming › 1D DP

Climbing stairs

Medium TUF ID 287 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A staircase has n steps. Each move climbs either 1 step or 2 steps. Count the distinct sequences of moves that end exactly on step n. Order matters: climbing 1 + 2 and 2 + 1 are two different ways.

Constraints: 1 ≤ n ≤ 45 on LeetCode, where the answer fits in an int. The Java methods return long, which keeps them exact up to n = 91, and they also accept n = 0.

Example 1

n = 3
answer = 3          // 1+1+1, 1+2, 2+1

Example 2

n = 5
answer = 8          // grouped by how many 2-steps are used, see below

For n = 5 the sequences use zero 2-steps (1 way), one 2-step among four moves (4 ways), or two 2-steps among three moves (3 ways).

Approach 1: Recursion

Intuition. Counting all sequences directly is awkward, so look at the last move instead. Any sequence that ends on step n finishes with either a 1-step from step n - 1 or a 2-step from step n - 2. Those two groups are disjoint (their last moves differ) and together they contain every valid sequence. So

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

The base cases are ways(1) = 1 (a single 1-step) and ways(0) = 1. The second one surprises people: there is exactly one way to climb zero steps, the empty sequence. It is not a trick; it is what makes ways(2) = ways(1) + ways(0) = 2 come out right (1 + 1 and 2).

This is the Fibonacci recurrence with different starting values: ways(n) = F(n + 1). Recognising that is useful, but the reasoning above is what transfers to other problems, because it does not depend on knowing the sequence in advance.

Algorithm.

  1. If n ≤ 1, return 1.
  2. Otherwise return ways(n - 1) + ways(n - 2).
static long recursive(int n) {
    if (n <= 1) return 1;                                   // step 0 or step 1: exactly one way
    return recursive(n - 1) + recursive(n - 2);
}

Complexity. Time O(2^n): each call branches twice, and the same ways(i) is recomputed many times (the call count itself grows like Fibonacci). Space O(n) for the recursion depth.

At n = 45 this is about 3.7 billion calls (2 · ways(n) - 1 in general). The test file runs it only up to n = 30.

Approach 2: Memoization

Intuition. There are only n + 1 different questions the recursion can ask: ways(0) through ways(n). Store each answer in an array the first time it is computed, and every later request becomes a lookup.

Algorithm.

  1. Create dp of size n + 1, filled with -1 (no real count is negative).
  2. In the recursive helper, return 1 for i ≤ 1, return dp[i] if it is filled, and otherwise compute ways(i - 1) + ways(i - 2), store it in dp[i], and return it.
static long memoization(int n) {
    long[] dp = new long[n + 1];
    Arrays.fill(dp, -1);                                    // -1 = not computed yet
    return ways(n, dp);
}

static long ways(int i, long[] dp) {
    if (i <= 1) return 1;
    if (dp[i] != -1) return dp[i];
    return dp[i] = ways(i - 1, dp) + ways(i - 2, dp);
}

Complexity. Time O(n): each state is computed once with O(1) work. Space O(n) for the table plus O(n) for the recursion stack.

Approach 3: Tabulation

Intuition. The recurrence only looks downward, at smaller steps. So fill the table from the ground up: once dp[i - 1] and dp[i - 2] exist, dp[i] is one addition away. No recursion means no risk of a stack overflow for large n.

Algorithm.

  1. dp[0] = 1, dp[1] = 1.
  2. For i from 2 to n, set dp[i] = dp[i - 1] + dp[i - 2].
  3. Return dp[n].

The array has at least two cells so that n = 0 can still write dp[1].

static long tabulation(int n) {
    long[] dp = new long[Math.max(n + 1, 2)];
    dp[0] = 1;                                              // standing on the ground: one way (do nothing)
    dp[1] = 1;                                              // a single 1-step
    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Complexity. Time O(n), space O(n).

Approach 4: Space optimized

Intuition. Step 2 of the tabulation reads only the two cells just below the one it writes. Keep those two numbers in variables and slide them up the staircase.

Algorithm.

  1. prev2 = 1 (ways to reach step 0), prev = 1 (ways to reach step 1).
  2. For i from 2 to n: cur = prev + prev2, then prev2 = prev, prev = cur.
  3. Return prev, which is ways(n). For n ≤ 1 the loop never runs and prev = 1 is already right.
static long spaceOptimized(int n) {
    long prev2 = 1, prev = 1;                               // ways(i - 2) and ways(i - 1), starting at i = 2
    for (int i = 2; i <= n; i++) {
        long cur = prev + prev2;
        prev2 = prev;
        prev = cur;
    }
    return prev;
}

Dry run for n = 5:

i prev2 before prev before cur prev2 after prev after
2 1 1 2 1 2
3 1 2 3 2 3
4 2 3 5 3 5
5 3 5 8 5 8

The answer is prev = 8.

Complexity. Time O(n), space O(1).

Edge cases and pitfalls