Climbing Stairs

You can climb 1 or 2 steps at a time. Return the number of distinct ways to reach the top with n steps. A naive recursion re-computes subproblems exponentially.

Why this is worth learning

Partition routes by their final move. A route ending in one step comes from n-1; one ending in two steps comes from n-2. These alternatives are disjoint and exhaustive.

Before coding: one-minute experiment

List the five ordered routes for n=4. Why are 1,2,1 and 2,1,1 different routes?

Function signature

func ClimbStairs(n int) int

Inputs / outputs

• n: number of steps.
• Return: number of distinct ways.

Example

n = 4
Ways: 1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2
Output: 5

Constraints

• 1 <= n <= 45

Core idea (near-solution)

The number of ways to reach step i is the sum of ways to reach i-1 and i-2.

Invariant: at iteration i, prev1 is ways for i-1 and prev2 for i-2.

Algorithm (step-by-step)

1. Handle base cases n <= 2.
2. Iterate i=3..n, updating rolling counts.
3. Return the last count.

Correctness sketch

Let F(i) count ordered sequences of ones and twos summing to i. Removing the final one-step move is a bijection with routes to i-1; removing a final two-step move is a bijection with routes to i-2. No route belongs to both classes, so F(i)=F(i-1)+F(i-2). The bases F(1)=1 and F(2)=2 are direct enumerations. Before computing i, the rolling variables hold exactly these preceding counts; assigning their sum and shifting preserves the invariant. Thus the returned value is F(n). The stated n<=45 bound fits a signed 32-bit int.

Trace (hand walkthrough)

Example input:
n = 4
Ways: 1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2
Output: 5

Walk:
- dp[0]=1, dp[1]=1
- dp[2]=2, dp[3]=3, dp[4]=5

Pitfalls to avoid

• Off-by-one in base cases.
• Using recursion without memoization.

Debugging lens

Check n=1 and n=2 before the loop. Preserve both old counts until the new count is formed. The mathematical empty-route base F(0)=1 is useful for derivation, but the existing API returns 0 for n=0, outside its stated positive-n domain.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Use two integers and update them in place.

Reconstruction checkpoint

List the five ordered routes for n=4. Why are 1,2,1 and 2,1,1 different routes?

Return to 1D DP (Including Kadane) · Module quiz