Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]

• Recurrence – dp[i] = dp[i-1] + dp[i-2], because the last move is either a single step from i-1 or a double step from i-2.
• Base cases – dp[0] = 1 (one way to stand at ground) and dp[1] = 1 (one way to reach step 1).
• Fibonacci identity – the sequence of way-counts is exactly the Fibonacci sequence shifted by one index.
• Rolling variables – since dp[i] depends only on the previous two, two variables replace the array.
• Complexity – O(n) time, O(1) space with rolling variables.

What is the Climbing Stairs problem?

You are given a staircase with n steps. At each step you can climb either one step or two steps. The question asks how many distinct ways you can reach the top. This is the gateway dynamic programming problem because it illustrates overlapping subproblems and optimal substructure in the simplest possible setting.

In banking, this maps to counting distinct progression paths through a loyalty tier ladder where members advance one or two tiers per qualifying action.

How does the recurrence work?

The last move into step i is either a single step from step i-1 or a double step from step i-2. These two groups of paths are disjoint (they differ in the last move) and together cover every possible path, so you add them: dp[i] = dp[i-1] + dp[i-2].

Base cases: there is one way to stand at the ground (do nothing), so dp[0] = 1. There is one way to reach step 1 (one single step), so dp[1] = 1.

package com.bank.service;

public class TierPathCounter {

    public static int countPaths(int n) {
        if (n <= 1) return 1;

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println("Ways to reach tier 5: " + countPaths(5));
        System.out.println("Ways to reach tier 10: " + countPaths(10));
    }
}

Ways to reach tier 5: 8
Ways to reach tier 10: 89

How do you optimise space with rolling variables?

Since dp[i] depends only on dp[i-1] and dp[i-2], you replace the array with two variables. This reduces space from O(n) to O(1).

public static int countPathsOptimised(int n) {
    if (n <= 1) return 1;

    int prev2 = 1; // dp[0]
    int prev1 = 1; // dp[1]

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

Why is this the Fibonacci sequence?

The recurrence f(n) = f(n-1) + f(n-2) with f(0) = 1, f(1) = 1 produces the Fibonacci numbers starting from index 1: 1, 1, 2, 3, 5, 8, 13, 21, ... The climbing stairs way-count for n steps equals the (n+1)-th Fibonacci number (depending on the indexing convention).

This means all properties of Fibonacci apply. The values grow exponentially (roughly as the golden ratio to the power n), which is why a naive recursive solution without memoisation has exponential time: it recomputes the same subproblems an exponential number of times.

// SLOW: naive recursion without memoisation
public static int countPathsSlow(int n) {
    if (n <= 1) return 1;
    return countPathsSlow(n - 1) + countPathsSlow(n - 2);
}
// Time: O(2^n) due to overlapping subproblems
// dp[5] calls dp[4]+dp[3], dp[4] calls dp[3]+dp[2], dp[3] is computed twice

How is this different from the k-step generalisation?

| Aspect | 1-or-2 Steps | Up to k Steps |
|---|---|---|
| Recurrence | dp[i] = dp[i-1] + dp[i-2] | dp[i] = sum of dp[i-1] through dp[i-k] |
| Identity | Fibonacci | k-step Fibonacci (Tribonacci for k=3) |
| Time | O(n) | O(n * k) or O(n) with a sliding window sum |
| Space | O(1) with 2 vars | O(k) with k rolling vars |

// Generalised: can climb 1, 2, ..., k steps
public static int countPathsKSteps(int n, int k) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int step = 1; step <= Math.min(i, k); step++) {
            dp[i] += dp[i - step];
        }
    }
    return dp[n];
}

What are the edge cases?

• n = 0 – you are already at the top, one way (do nothing).
• n = 1 – one way: a single step.
• n = 2 – two ways: (1+1) or (2).
• Large n – values grow exponentially and can overflow an int. For n > 46, the result exceeds Integer.MAX_VALUE. Use long or BigInteger.

// Edge case: overflow for large n
public static long countPathsLong(int n) {
    if (n <= 1) return 1L;
    long prev2 = 1L, prev1 = 1L;
    for (int i = 2; i <= n; i++) {
        long current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}
// n=50 -> 20365011074 (exceeds int range)

What are common mistakes?

The most common mistake is using naive recursion without memoisation, leading to exponential time.

// WRONG: exponential time
public static int slow(int n) {
    if (n <= 1) return 1;
    return slow(n - 1) + slow(n - 2); // recomputes subproblems
}

// CORRECT: memoised top-down
public static int fast(int n, int[] memo) {
    if (n <= 1) return 1;
    if (memo[n] != 0) return memo[n];
    memo[n] = fast(n - 1, memo) + fast(n - 2, memo);
    return memo[n];
}

Another mistake is getting the base cases wrong. Setting dp[0] = 0 instead of 1 makes every count off by one.

What is the time and space complexity?

The bottom-up array version is O(n) time and O(n) space. The rolling-variable version is O(n) time and O(1) space. The naive recursive version is O(2^n) time and O(n) stack space. Memoisation brings the top-down version to O(n) time and O(n) space.

What should a senior engineer know?

A senior engineer should know that Climbing Stairs is the template for all linear recurrence DP problems. The pattern of "sum the previous k results" appears in decode ways, tiling problems, and tribonacci.

They should also know the matrix exponentiation approach: the Fibonacci recurrence can be expressed as a 2x2 matrix multiplication, and computing the n-th Fibonacci in O(log n) time using fast matrix exponentiation is a classic optimisation.

// Matrix exponentiation for O(log n) Fibonacci
// [F(n+1), F(n)] = [[1,1],[1,0]]^n * [F(1), F(0)]
// Useful when n is very large (millions)