Climbing Stairs
Determine the number of distinct ways to reach the top of a staircase by taking 1 or 2 steps at a time.
Ready
Stairs N =
5
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
If you are at step n, you must have come from either step n-1 (taking 1 step) or step n-2 (taking 2 steps). Thus, the number of ways to reach step n is simply the sum of ways to reach the two previous steps. This structure is identical to the Fibonacci sequence.
Concept
Recurrence Relation:
Ways(n) = Ways(n-1) + Ways(n-2)
Base Cases:
- Ways(0) = 1 (Standing on the ground is 1 way)
- Ways(1) = 1 (One step to reach step 1)
- Ways(2) = 2 (1+1 or 2)
This is a classic 1D Dynamic Programming problem where the state depends only on the previous two states.
How it Works
Tabulation Algorithm:
- Initialize an array `dp` of size n+1.
- Set `dp[0] = 1`, `dp[1] = 1`.
- Iterate from i = 2 to n.
- For each step, set `dp[i] = dp[i-1] + dp[i-2]`.
- The answer is `dp[n]`.
Step-by-Step Breakdown
Visualizing the path:
- Step 0 & 1: Fixed starting points.
- Step 2: Sum of Step 1 and Step 0.
- Step 3+: Rolling sum of the previous two values.
When to Use
Applications:
- Counting permutations with restricted step sizes.
- Foundation for more complex "path counting" problems (e.g., Min Cost Climbing Stairs).
When NOT to Use
- Variable Steps: If step sizes change dynamically, the simple 2-state relation breaks (though DP still applies with modification).
How to Identify
"Count distinct ways", "Review previous choices".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.