Climbing Stairs Problem
What you'll learn: How to count all the different ways you can climb a staircase by taking 1 or 2 steps at a time using dynamic programming.
The Problem
Imagine you're at the bottom of a staircase with n steps. Each move, you can either climb 1 step or 2 steps. How many distinct ways can you reach the top?
For example, with 3 steps, there are 3 ways:
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
Why It's Perfect for DP
This problem has overlapping subproblems and optimal substructure. To reach step n, you must have come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). So:
ways(n) = ways(n-1) + ways(n-2)
Sound familiar? It's the Fibonacci pattern! But we're counting paths, not generating numbers.
The Solution
Base cases:
ways(0) = 1(one way to stay at ground: do nothing)ways(1) = 1(only one 1-step)
Bottom-up approach: Build a table from step 0 upward, filling each entry by adding the previous two values—just like the Fibonacci sequence with memoization or tabulation.
Analogy
Think of it like routing options on a map: the number of paths to destination n equals all paths to the previous two waypoints combined.
Key Takeaway: The Climbing Stairs problem is essentially Fibonacci in disguise—use dynamic programming to avoid recalculating overlapping subproblems, achieving O(n) time and O(1) space with optimization.