You climb a staircase with n steps, taking either 1 or 2 steps at a time. Count the number of distinct ways to reach the top.
DSA Animator › DSA Revision › Dynamic Programming › Climbing Stairs
Remember: ask where the last move came from. The recurrence is the sum of the ways into the previous states. The video solves Climbing Stairs (LeetCode 70, Easy) with the 1D DP pattern from the Dynamic Programming topic, and you can replay every step in the interactive Climbing Stairs animation.
You climb a staircase with n steps, taking either 1 or 2 steps at a time. Count the number of distinct ways to reach the top.
For n equal to 5, there are 8 ways. For n equal to 3, the 3 ways are 1 1 1, then 1 2, then 2 1.
Listing every sequence of 1 and 2 steps grows exponentially. But the count for each step can be built from smaller counts.
Think about the very last move to step i. Either you came from step i minus 1 with a single step, or from step i minus 2 with a double step. So ways of i equals ways of i minus 1 plus ways of i minus 2. The base cases are 1 way to reach step 1, and 2 ways to reach step 2. It is the Fibonacci pattern in disguise.
Step 1 has 1 way, and step 2 has 2 ways. Step 3 has 2 plus 1, which is 3 ways. Step 4 has 3 plus 2, which is 5 ways. Step 5 has 5 plus 3, which is 8 ways. So there are 8 ways to climb 5 steps.
In code, return n when n is at most 2. Keep the counts for the previous two steps. Loop from 3 to n, adding them and shifting forward. It's O of n time and O of 1 space.
Remember: ask where the last move came from. The recurrence is the sum of the ways into the previous states.