Count Ways to Climb a Staircase

A staircase has N steps. From any step you may advance by either 1 step or 2 steps at a time, starting from the ground (step 0) and finishing exactly on step N. Using a recursive function with memoization (to avoid recomputing overlapping subproblems), compute the number of distinct sequences of moves that reach step N exactly.

Input: A single line containing the integer N. Output: A single line containing the number of distinct ways to climb N steps.

1 <= N <= 45.

This is a canonical, foundational example of WHY memoization matters - without it, a perfectly correct recursive formula still runs in exponential time due to redundant recomputation of the exact same sub-problems, again and again.

Count the number of distinct ways to climb a staircase, taking 1 or 2 steps at a time, using recursion with memoization. Brute force: Compute ways(N) via plain recursion WITHOUT memoization - this branches exponentially (each call spawns two more), recomputing the SAME smaller values over and over, costing O(2^N) time despite there being only N+1 distinct sub-problems. Optimised: Memoizing each ways(k) the first time it's computed (caching it in an array) ensures every distinct sub-problem is solved EXACTLY ONCE, no matter how many times it's requested by different recursive branches - turning exponential recomputation into linear time, since there are only N+1 distinct values of k ever needed.

1. The RECURSIVE RELATION: ways(N) = ways(N-1) + ways(N-2), since the LAST move taken to reach step N was either a single 1-step (from step N-1) or a 2-step (from step N-2). 2. The BASE CASES: ways(0) = 1 (one way to already be at the top with no moves taken), ways(1) = 1. 3. MEMOIZE each computed ways(k) the first time it's computed, so repeated calls with the same k return instantly instead of recomputing.

Time: O(N) with memoization - each of the N+1 distinct sub-problems is computed once; O(2^N) without memoization. Space: O(N), for the memoization array (plus O(N) recursion stack depth).

N = 1 has exactly 1 way. N = 2 has exactly 2 ways (1+1 or 2). Without memoization the naive recursion is exponential, and N = 45 would be far too slow - memoization is required to finish quickly.

Be ready to point out that this recurrence is EXACTLY the Fibonacci sequence's recurrence (ways(N) = ways(N-1) + ways(N-2)) - recognizing this connection instantly signals you understand the problem's underlying structure, not just its surface description.