Climbing Stairs - Video Solutions

Problem Overview: You are given n stairs. Each move allows either 1 step or 2 steps. The task is to compute the total number of distinct ways to reach the top. This is a classic recurrence problem where the number of ways to reach step i depends on the previous two steps.

Approach 1: Recursive with Memoization (Time: O(n), Space: O(n))

The recurrence relation is straightforward: to reach step n, you either come from step n-1 with a single step or from step n-2 with a double step. That leads to ways(n) = ways(n-1) + ways(n-2). A naive recursive solution recomputes the same subproblems repeatedly, resulting in exponential time. Memoization fixes this by storing results in a cache (array or hash map) and returning the stored value when the function encounters the same input again.

This turns the recursion into a top‑down dynamic programming solution. Each state is computed exactly once, giving O(n) time complexity and O(n) space for the memo table plus recursion stack. This approach is useful when you want to express the solution directly from the recurrence and let memoization handle repeated work.

Approach 2: Dynamic Programming (Bottom-Up) (Time: O(n), Space: O(n))

The same recurrence can be solved iteratively. Create a DP array where dp[i] represents the number of ways to reach step i. Initialize the base cases: dp[1] = 1 and dp[2] = 2. Then iterate from 3 to n, computing dp[i] = dp[i-1] + dp[i-2]. Each iteration builds on previously computed states.

This bottom‑up dynamic programming approach avoids recursion and stack overhead. The recurrence is identical to the Fibonacci sequence, which is why this problem frequently appears in discussions of math patterns in DP problems. The algorithm performs a single pass through the array, giving O(n) time and O(n) space.

The space can also be optimized to O(1) by keeping only the last two values instead of the entire array. Since each state depends only on the previous two, two variables are sufficient to compute the sequence iteratively.

Recommended for interviews: Interviewers expect the dynamic programming interpretation. Starting with the recursive recurrence shows you understand the problem structure, especially if you mention memoization to eliminate repeated work. The strongest answer moves quickly to the bottom‑up DP or constant‑space Fibonacci-style iteration because it demonstrates recognition of the pattern and optimal implementation.