Stairs (Climbing Stairs)
Topic: Group 11 - Dynamic Programming
Difficulty: Easy
Links: LeetCode 70
Problem Description
You are climbing a staircase. It takes \(n\) steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
1. Logical Breakdown
This problem is a classic example of Dynamic Programming because it has optimal substructure and overlapping subproblems.
- The Decision: At any step \(i\), you could have arrived there from step \(i-1\) (taking 1 step) or step \(i-2\) (taking 2 steps).
- The Accumulation: Therefore, the total ways to reach step \(i\) is simply the sum of the ways to reach the two previous steps.
- The Pattern: If we calculate this for \(n=1, 2, 3, 4, 5\), we get the sequence \(1, 2, 3, 5, 8...\). This is exactly the Fibonacci Sequence.
2. Recurrence Relation
Let \(f(n)\) be the number of ways to reach step \(n\).
\[f(n) = f(n-1) + f(n-2)\]
Base Cases: * \(f(1) = 1\) (Only 1 way: [1]) * \(f(2) = 2\) (Ways: [1,1], [2])
3. Complexity Analysis
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force (Recursion) | \(O(2^n)\) | \(O(n)\) | Too slow. Recalculates same states repeatedly. |
| DP (Tabulation) | \(O(n)\) | \(O(n)\) | Uses an array dp[] to store values. |
| Space Optimized | \(O(n)\) | \(O(1)\) | (Recommended) We only need the last two variables (prev1, prev2). |
| Matrix Exponentiation | \(O(\log n)\) | \(O(1)\) | Useful for huge \(N\). |