Count the Number of Ways to Reach the Nth Stair

The staircase problem asks how many distinct ways exist to climb n stairs if each move covers either one or two stairs at a time.

It’s a standard placement coding question for two reasons: the naive recursion is immediately obvious, but every interviewer expects you to optimise it. The journey from O(2^n) to O(1) space covers the full arc of dynamic programming thinking in roughly 30 lines of code.

Problem Statement

A person stands at the bottom of a staircase with n steps. Each move takes either one step or two steps. Count the total number of distinct ways to reach the top.

For n=4, enumerated directly:

• (1, 1, 1, 1) — four moves of one step each
• (1, 1, 2) — two single steps, then a double
• (1, 2, 1) — single, double, single
• (2, 1, 1) — double, then two singles
• (2, 2) — two double steps

Total: 5 ways. The recurrence reveals itself: to stand on stair n, you arrived either from stair n-1 (one step) or stair n-2 (two steps). So the count satisfies f(n) = f(n-1) + f(n-2), with base cases f(0)=1 and f(1)=1.

That recurrence matches the Fibonacci sequence exactly. Verified values for small n:

n	f(n)	Derivation
0	1	base case (stand at ground)
1	1	base case (one step forced)
2	2	f(1) + f(0) = 1 + 1
3	3	f(2) + f(1) = 2 + 1
4	5	f(3) + f(2) = 3 + 2
5	8	f(4) + f(3) = 5 + 3
6	13	f(5) + f(4) = 8 + 5

Recursive Solution

The most direct translation of the recurrence into code:

def count_ways(n):
    if n <= 1:
        return 1
    return count_ways(n - 1) + count_ways(n - 2)

This works correctly for all n, but the cost is steep. To compute f(5), the function calls f(4) and f(3). f(4) itself calls f(3) and f(2). So f(3) is computed twice, f(2) three times, f(1) five times. The call tree roughly doubles in size with each additional stair.

More concretely, the call counts grow fast:

• f(10) requires 177 total recursive calls
• f(20) requires 21,891 calls
• f(40) exceeds a billion calls

The count grows as O(2^n), making this version useless for any n above roughly 40 on a standard machine with a 1-second time limit.

Stack depth equals n, since each recursive frame waits for its two children to return. Space complexity: O(n) from the call stack alone, even before counting return values.

Memoization: Top-Down DP

The recursive solution recomputes f(3) twice, f(2) three times, and so on. Memoization stores each computed value and returns it immediately on a second lookup.

from functools import lru_cache

@lru_cache(maxsize=None)
def count_ways_memo(n):
    if n <= 1:
        return 1
    return count_ways_memo(n - 1) + count_ways_memo(n - 2)

Or explicitly with a dictionary, which makes the cache visible:

def count_ways_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return 1
    memo[n] = count_ways_memo(n - 1, memo) + count_ways_memo(n - 2, memo)
    return memo[n]

Each value from f(0) to f(n) is computed exactly once and stored. Subsequent lookups cost O(1). Time complexity: O(n). Space complexity: O(n) (memo dictionary plus call stack depth of n).

The improvement over naive recursion is the same principle that separates brute-force exhaustive search from a well-designed algorithm: identify overlapping sub-problems and compute them once.

Bottom-Up Tabulation

The memoized approach still uses O(n) stack space from recursion. Bottom-up tabulation removes the recursion entirely by filling values in order from the base cases upward.

def count_ways_dp(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

The loop fills dp[0] through dp[n] in order. No recursion, no stack frames, no risk of hitting Python’s default recursion limit for large n. Time: O(n). Space: O(n) for the dp array. For most placement coding rounds, this is the expected clean solution.

The pattern here is identical to the approach used for other array-based recurrences, such as the equilibrium index problem, where computing prefix sums bottom-up avoids repeated work across the array.

Space-Optimised Solution

The tabulation array stores n+1 values, but at each step only dp[i-1] and dp[i-2] matter. Everything else is dead weight. Two variables are enough.

def count_ways_optimised(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1   # f(0), f(1)
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

Time: O(n). Auxiliary space: O(1).

The space saving is significant for large n. The full dp array of size n+1 grows linearly; the two-variable version uses a fixed number of registers regardless of n. Understand this alongside space complexity of algorithms to get a clear mental model of what “auxiliary space” means in memory-constrained online judges.

The reduction from O(n) auxiliary space (full dp array) to O(1) (two variables) is a clean instance of the rolling-window pattern: when a recurrence depends only on a fixed number of prior values, a rolling window replaces the array without any loss in correctness.

Solution complexity summary

Approach	Time	Auxiliary space
Naive recursion	O(2^n)	O(n) (call stack)
Memoization (top-down)	O(n)	O(n) (memo + stack)
Bottom-up tabulation	O(n)	O(n) (dp array)
Space-optimised (rolling)	O(n)	O(1)

Variations Worth Knowing

k Steps at a Time

When each move can cover 1 through k stairs, the recurrence extends:

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

Tabulation handles this with a nested loop:

def count_ways_k_steps(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for step in range(1, k + 1):
            if i - step >= 0:
                dp[i] += dp[i - step]
    return dp[n]

Time is O(n * k). For small fixed k this is effectively O(n).

Forbidden Stairs

If certain stair positions are blocked, add a conditional in the tabulation loop:

def count_ways_forbidden(n, blocked):
    blocked_set = set(blocked)
    dp = [0] * (n + 1)
    dp[0] = 1 if 0 not in blocked_set else 0
    for i in range(1, n + 1):
        if i in blocked_set:
            dp[i] = 0
        else:
            dp[i] = dp[i - 1] + (dp[i - 2] if i >= 2 else 0)
    return dp[n]

Both variations appear in placement coding rounds at Tier-2 and Tier-3 colleges. The key skill they test is whether you can extend a base recurrence without rebuilding the solution from scratch.

The leap from O(2^n) naive recursion to memoized DP to O(1) space is exactly the problem-decomposition instinct that AI engineering builds on. TinkerLLM is the entry point to apply that instinct to LLM workflows at ₹299, starting from the same trade-off between computation cost and memory that the space-optimised staircase solution demonstrates.