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.

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

• Invariant: at iteration i, prev1 is ways for i-1 and prev2 for i-2.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

Complexity

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

Implementation notes (Go)

• Use two integers and update them in place.