Climbing Stairs

Difficulty: Easy

Problem

A staircase has n steps, and each move lifts you by either 1 or 2 steps. Work out how many different sequences of moves take you from the ground to the very top. This is a first dynamic programming exercise, and you can follow the full path from plain recursion to memoization to tabulation.

Example

Input: n = 5
Output: 8
Explanation: Some of the 8 ways: 1+1+1+1+1, 1+1+1+2, 1+2+2, 2+2+1, 2+1+2. Order matters, 1+1+2 and 2+1+1 use the same hops but touch different stairs on the way up, so they count as distinct ways.

Brute-force approach

The naive recursion IS taught inside the guided walkthrough: watch it explode, then fix it twice.

Optimal approach

Key insight: ways(n) = ways(n−1) + ways(n−2): the last hop was 1 or 2. Cure the exponential recursion with a notebook, then flip it into a table.

Run the full arc from foundations on your first real problem: write the honest recursion, watch it go exponential, memoize it down to O(n), then flip it into a bottom-up table, with the O(1) rolling-variable finale waiting at the end.

Steps

Frame it with the framework: STATE dp[i] = ways to reach step i; TRANSITION dp[i] = dp[i−1] + dp[i−2]; BASE dp[0] = dp[1] = 1
Write the naive recursion: correct by construction, but O(2ⁿ) from recomputed subproblems
Memoize: check the notebook at the door, record before returning, O(n) time
Tabulate: seed dp[0] and dp[1], loop 2..n filling left to right, answer at dp[n]
Finale: the transition's reach is 2, so two rolling variables replace the table, O(1) space

Time complexity: O(n) · Space complexity: O(n) table: O(1) with rolling variables

Pseudocode

function climbStairs(n):
    // STATE: dp[i] = distinct ways to reach step i
    if n <= 1:
        return 1
    dp = new array of size n + 1
    dp[0] = ____      // ways to stand at the bottom
    dp[1] = ____      // ways to reach step 1
    
    for i from 2 to n:
        dp[i] = ____ + ____      // last hop was 1 or 2
    
    return ____

Hints

How many ways to be standing at the bottom before any hop? Exactly one: the do-nothing climb. dp[0] = 0 is the classic wrong turn that shorts every later count.
Step 1 is reachable only by a single 1-hop. Check both bases against the state sentence: 'dp[i] = distinct ways to reach step i'.
Case-split the LAST hop: a 1-hop arrives from i−1, a 2-hop from i−2. The two groups are disjoint and cover everything, counting questions ADD their branches.
The big question is 'ways to reach step n'. Return whichever slot the state sentence says holds it.

Complexity questions

What is the time complexity of the naive recursion?

O(2ⁿ): each call branches into two more, so the calls roughly double per level. Every non-base call spawns two children, and the call tree runs about n levels deep, doubling per level lands at O(2ⁿ). Concretely: n = 10 costs 177 calls, n = 40 about 1.6 billion. The repeated subproblems are the entire cause.

After adding the memo, or flipping to the table, what is the time complexity?

O(n): each of the n+1 subproblems is computed exactly once. There are only n+1 distinct subproblems (ways(0) through ways(n)), and both cures guarantee each is computed once. Every further encounter is an O(1) lookup or slot read. That's DP's promise: time proportional to DISTINCT states, not to the naive call count.

Why can the O(n) table shrink to O(1) space?

Because the transition reaches back only 2 slots, dp[i−1] and dp[i−2], so two rolling variables carry everything the next computation needs. Audit the reach: dp[i] never reads anything older than dp[i−2], so every slot behind that window is dead weight. Keep prev2 and prev1, roll them forward each iteration, and memory stays at two integers: the foundations rule 'reach of k → k variables' in action.

Which problems share this exact 'two backward reaches' shape?

Fibonacci, Min Cost Climbing Stairs, and Decode Ways, 1D states whose transition reaches back one and two slots. Same skeleton, different costumes: fib SUMS the two previous values, Min Cost Climbing Stairs takes a MIN over the same two reaches, Decode Ways sums them behind validity checks on the digits. Master the shape once and the whole family falls.

Check your understanding of Climbing Stairs

You climb 1 then 2; your friend climbs 2 then 1. Same staircase, same two hop sizes. One way or two?

Two: a way is the ordered SEQUENCE of hops, so different orderings are different ways. A way is the full ordered sequence of hops. 1+2 touches step 1 then step 3; 2+1 touches step 2 then step 3: physically different climbs. Distinct orderings count separately, which is exactly why n = 3 has 3 ways rather than 2.

Trace n = 3 by hand. How many distinct ways are there?

3. List them: 1+1+1, 1+2, and 2+1. Three ways, and notice 1+2 and 2+1 both appear because orderings are distinct. Sanity check against the recurrence: ways(3) = ways(2) + ways(1) = 2 + 1 = 3 ✓.

Stand at the top (step n) and look backwards: how did the FINAL hop of any climb arrive?

Either a 1-hop from step n−1 or a 2-hop from step n−2, nothing else, so ways(n) = ways(n−1) + ways(n−2). Hops only come in sizes 1 and 2, so the last hop launched from n−1 or n−2, there is no third option. Every way to reach n−1 extends uniquely with a 1-hop, every way to reach n−2 with a 2-hop, and the two groups can't overlap (their last hops differ). Add them: this is the last-step trick from foundations, rediscovered.

The recursion ways(n) = ways(n−1) + ways(n−2) is correct. Why is it painfully slow when coded naively?

It recomputes the SAME subproblems over and over, ways(3) appears in both branches of ways(5), and the doubling per level makes it O(2ⁿ). It's fib's disease from foundations, verbatim: ways(5) calls ways(4) and ways(3), and ways(4) calls ways(3) AGAIN, twin subtrees doing identical work. Each +1 on n roughly doubles the calls; climbStairs(40) makes about 1.6 billion. The answers never change, so all that repetition is pure waste.

What are the base cases, and how do you know they're right?

dp[0] = 1 and dp[1] = 1. One way to stand at the bottom (do nothing) and one way to reach step 1 (a single 1-hop); both check out against the state sentence. Check each against the sentence 'dp[i] = the number of distinct ways to reach step i'. Ways to reach step 0: just stand there, exactly one, the empty climb. Ways to reach step 1: a single 1-hop, no alternative. dp[0] = 0 is the classic trap. It would make every later count come out short.