Climbing Stairs

Difficulty: Easy

Problem

You are climbing a staircase with n steps. Each hop takes you up either 1 step or 2 steps. Count how many DISTINCT ways there are to climb from the bottom to the top. Your first DP problem — the full arc from foundations (naive recursion → memoization → tabulation) runs end to end right here.

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

  1. 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
  2. Write the naive recursion — correct by construction, but O(2ⁿ) from recomputed subproblems
  3. Memoize: check the notebook at the door, record before returning — O(n) time
  4. Tabulate: seed dp[0] and dp[1], loop 2..n filling left to right, answer at dp[n]
  5. 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