Staircase (Count Ways to Climb N Stairs Taking 1, 2, or 3 Steps)

• Staircase problem – count the distinct ways to reach the top of an N-step staircase taking 1, 2, or 3 steps at a time.
• Recurrence – dp[n] = dp[n-1] + dp[n-2] + dp[n-3], a three-term Fibonacci generalisation.
• Base cases – dp[0] = 1 (standing still), dp[1] = 1 (one step), dp[2] = 2 (1+1 or 2).
• Rolling variables – three variables slide forward for O(n) time and O(1) space.
• Generalisation – if K step sizes are allowed, the recurrence sums over all K sizes.
• Overflow – counts grow exponentially; use BigInteger for large N.

What is the staircase problem?

You are climbing a staircase with N steps. At each move, you can take one step, two steps, or three steps. The question asks how many distinct sequences of moves reach the top. Order matters: taking 1 then 2 is different from taking 2 then 1.

This is a counting problem in the Fibonacci Numbers DP pattern, generalised from two terms to three.

package com.bank.dsa;

public class StaircaseThreeStep {

    public static long countWays(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;

        long a = 1, b = 1, c = 2;  // dp[0], dp[1], dp[2]
        for (int i = 3; i <= n; i++) {
            long next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            System.out.println("stairs(" + n + ") = " + countWays(n));
        }
    }
}

stairs(0) = 1
stairs(1) = 1
stairs(2) = 2
stairs(3) = 4
stairs(4) = 7
stairs(5) = 13
stairs(6) = 24
stairs(7) = 44
stairs(8) = 81
stairs(9) = 149
stairs(10) = 274

Why does the recurrence sum three terms?

To land on step N, the final move must have come from step N-1 (a one-step), step N-2 (a two-step), or step N-3 (a three-step). These three groups of sequences are completely separate because they end with different final moves. So the total ways to reach step N is the sum of the ways to reach those three predecessor steps.

This is the same logic as the two-step climbing stairs (which sums two terms and gives Fibonacci), extended by one more term.

How do the base cases work?

The base cases must be defined carefully because the recurrence reaches back three positions:

• dp[0] = 1: there is exactly one way to stand at the bottom without moving.
• dp[1] = 1: the only way to reach step 1 is a single one-step.
• dp[2] = 2: reach step 2 by either 1+1 or a single two-step.

From step 3 onward, the recurrence dp[n] = dp[n-1] + dp[n-2] + dp[n-3] takes over.

package com.bank.dsa;

public class StaircaseBaseCases {

    public static void verify() {
        // Step 3: 1+1+1, 1+2, 2+1, 3 → 4 ways
        System.out.println("dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = " + (2 + 1 + 1));
        // Step 4: 7 ways
        System.out.println("dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = " + (4 + 2 + 1));
    }

    public static void main(String[] args) {
        verify();
    }
}

dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4
dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7

How does this generalise to K step sizes?

If you can take steps of sizes from a given set (like {1, 3, 5}), the recurrence becomes dp[n] = sum of dp[n - step] for each allowed step. This is identical to the coin-change counting problem.

package com.bank.dsa;

public class StaircaseGeneralised {

    public static long countWays(int n, int[] steps) {
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int step : steps) {
                if (step <= i) {
                    dp[i] += dp[i - step];
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println("Steps {1,2,3}, n=5: " + countWays(5, new int[]{1, 2, 3}));
        System.out.println("Steps {1,3,5}, n=5: " + countWays(5, new int[]{1, 3, 5}));
    }
}

Steps {1,2,3}, n=5: 13
Steps {1,3,5}, n=5: 5

How is this different from the two-step climbing stairs?

| Aspect | Two-step (1 or 2) | Three-step (1, 2, or 3) |
|---|---|---|
| Recurrence terms | dp[n-1] + dp[n-2] | dp[n-1] + dp[n-2] + dp[n-3] |
| Rolling variables | 2 | 3 |
| Base cases | dp[0]=1, dp[1]=1 | dp[0]=1, dp[1]=1, dp[2]=2 |
| Sequence | 1, 1, 2, 3, 5, 8... (Fibonacci) | 1, 1, 2, 4, 7, 13, 24... (Tribonacci) |
| Growth rate | Golden ratio (~1.618) | Tribonacci constant (~1.839) |

What are common mistakes?

The most frequent mistake is getting the base cases wrong. If dp[0] is set to 0 instead of 1, the entire sequence shifts incorrectly because the recurrence builds on a wrong foundation.

// WRONG: dp[0] = 0 means reaching step 3 by a single three-step is not counted
long a = 0, b = 1, c = 2;
// dp[3] = 0 + 1 + 2 = 3 (should be 4)

// CORRECT: dp[0] = 1 counts the "do nothing" sequence at the bottom
long a = 1, b = 1, c = 2;
// dp[3] = 1 + 1 + 2 = 4

Another mistake is using an array when only three variables are needed, wasting O(n) space for no benefit.

What about overflow?

The counts grow exponentially (roughly 1.839^n for the tribonacci-like sequence). A long overflows around n = 63 for this recurrence. For large N, use BigInteger.

package com.bank.dsa;

import java.math.BigInteger;

public class StaircaseBigInteger {

    public static BigInteger countWays(int n) {
        if (n == 0) return BigInteger.ONE;
        if (n == 1) return BigInteger.ONE;
        if (n == 2) return BigInteger.TWO;

        BigInteger a = BigInteger.ONE, b = BigInteger.ONE, c = BigInteger.TWO;
        for (int i = 3; i <= n; i++) {
            BigInteger next = a.add(b).add(c);
            a = b;
            b = c;
            c = next;
        }
        return c;
    }

    public static void main(String[] args) {
        System.out.println("stairs(100) = " + countWays(100));
    }
}

stairs(100) = 180396380815100901214157639

When should you use this in banking?

At the National Bank of India, a multi-stage loan approval process allows actions that advance by one, two, or three stages. The process-design team counts the distinct action sequences to understand how many valid paths exist through the workflow, which helps in capacity planning and audit trail analysis.

package com.bank.service;

public class ApprovalPathCounter {

    public static long countPaths(int totalStages) {
        if (totalStages == 0) return 1;
        if (totalStages == 1) return 1;
        if (totalStages == 2) return 2;

        long a = 1, b = 1, c = 2;
        for (int i = 3; i <= totalStages; i++) {
            long next = a + b + c;
            a = b;
            b = c;
            c = next;
        }
        return c;
    }

    public static void main(String[] args) {
        System.out.println("Paths for 5-stage approval: " + countPaths(5));
        System.out.println("Paths for 10-stage approval: " + countPaths(10));
    }
}

Paths for 5-stage approval: 13
Paths for 10-stage approval: 274

What should a senior engineer know?

A senior engineer should recognise that this is a tribonacci sequence (three-term Fibonacci). Just as Fibonacci has a matrix exponentiation solution in O(log n), tribonacci has a 3x3 matrix version that computes the answer in O(log n) time. This is rarely needed in practice but shows depth.

The generalisation to arbitrary step sizes transforms the problem into a linear recurrence whose order equals the number of distinct step sizes. When the step sizes are given as input (not fixed at 1, 2, 3), the problem becomes equivalent to the permutation-style coin change count, and the amount loop must be outer with the step loop inner.