214. Climbing Stairs - Count Ways

Given a staircase with n steps, and being able to climb either 1 or 2 steps at a time, count the number of distinct ways to reach the top.

Input: A single line contains the integer n, the number of steps. Output: Print a single integer - the number of distinct ways to climb to the top.

1 <= n <= 45

Recognizing 'this problem's recurrence is just Fibonacci in disguise' is a valuable pattern-matching skill - many seemingly different counting problems reduce to this exact same additive recurrence shape.

Count the number of distinct ways to climb a staircase of n steps, taking 1 or 2 steps at a time. Brute force: Recursively try every combination of 1s and 2s summing to n, without memoization - this recomputes the SAME sub-problems repeatedly (e.g. ways(5) needed by both ways(6) and ways(7)), causing exponential blowup. Optimised: Since ways(n) only depends on the two immediately preceding values, building the sequence bottom-up (or memoizing top-down) computes each distinct sub-problem exactly once, turning exponential recursion into a single O(n) linear pass.

Notice that computing ways(n) only ever needs the previous two values, never anything further back, so instead of keeping a full array just keep two running variables and slide them forward one step at a time until reaching n. This produces the exact same result as the array-based DP but drops the memory usage from linear to constant, which matters once n approaches its upper bound. Time: O(n) Space: O(1)

Use the same recurrence ways(n) = ways(n-1) + ways(n-2), but store every computed value in an array (or memoize it) so each value from 0 to n is computed exactly once and reused whenever it's needed again. This removes all the repeated recursive work of the brute-force version, turning an exponential blow-up into a single linear pass, at the cost of keeping the whole array of intermediate results around. Time: O(n) Space: O(n)

Define ways(n) as ways(n-1) + ways(n-2), since the last move to reach step n was either a single step from n-1 or a double step from n-2, with base cases ways(0)=1 and ways(1)=1, and evaluate this recurrence with plain recursive calls and no caching. This is correct because it directly mirrors the problem's recursive structure, but the same subproblems get recomputed exponentially many times as the recursion branches. Time: O(2^n) Space: O(n)

1. The last move to reach step n is either a SINGLE step from step n-1, or a DOUBLE step from step n-2. 2. So ways(n) = ways(n-1) + ways(n-2) - exactly the Fibonacci recurrence, shifted. 3. Base cases: ways(1)=1, ways(2)=2, built up bottom-to-top from there.

Time: O(n) - one pass building up from ways(1) and ways(2). Space: O(1) - only the previous two values need to be kept in memory at any time.

Test n = 1 (1 way) and n = 45 (upper bound), where the Fibonacci-like growth still fits a standard integer type.

This is often the very FIRST dynamic programming problem taught - be ready to explicitly connect it to the Fibonacci sequence, and to explain clearly why naive recursion without memoization is exponential.