Problem Statement
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?
Example 1
- Input:
n = 2
- Output:
2
- Explanation:
There are two ways to climb to the top:
- 1 step + 1 step
- 2 steps
Example 2
- Input:
n = 3
- Output:
3
- Explanation:
There are three ways to climb to the top:
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
Constraints
Approach
a. Brute Force (Recursive)
Steps:
- Base Cases:
- If
n == 0, there is 1 way to stay at the bottom (no steps needed).
- If
n == 1, there is 1 way to climb one step.
- Recursive Case:
- For
n > 1, the number of ways to reach the n-th step is the sum of ways to reach (n-1)-th step and (n-2)-th step.
- This is because from the
(n-1)-th step, you can take 1 step to reach n, and from the (n-2)-th step, you can take 2 steps to reach n.
- Implementation:
- Implement the above logic using a recursive function.
Time & Space Complexity:
- Time Complexity: O(2ⁿ)
Each call branches into two more calls, leading to an exponential number of calls.
- Space Complexity: O(n)
The maximum depth of the recursion stack is n.
Code Snippet:
Dry Run:
Let's perform a dry run for n = 3.
So, there are 3 distinct ways to climb to the top when n = 3.
b. Optimized Approach (Dynamic Programming - Memoization)
Steps:
- Base Cases:
- If
n == 0 or n == 1, return 1.
- Memoization:
- Use a memo object to store the number of ways to reach each step.
- Before computing the number of ways for a particular
n, check if it is already in the memo.
- If it is, return the stored value to avoid redundant calculations.
- Recursive Case with Memoization:
- For
n > 1, compute the number of ways by summing the ways to reach (n-1)-th and (n-2)-th steps.
- Store the result in the memo before returning it.
- Implementation:
- Implement the above logic using a recursive function enhanced with memoization.
Time & Space Complexity:
- Time Complexity: O(n)
Each subproblem is solved only once and stored in the memo.
- Space Complexity: O(n)
The memo object stores results for each step up to n, and the recursion stack can go as deep as n.
Code Snippet:
Dry Run:
Let's perform a dry run for n = 3 with memoization.
Additionally, the memo after the computation would be {2: 2, 3: 3}.
So, there are 3 distinct ways to climb to the top when n = 3.
Complexity Analysis
Conclusion
When solving problems like climbing stairs, it's essential to analyze the approach you take. The brute force method, while straightforward, can quickly become inefficient as the input size grows due to its exponential time complexity. On the other hand, the optimized dynamic programming approach using memoization significantly reduces the time complexity by storing and reusing the results of subproblems.
Key Takeaways:
- Brute Force is simple but often inefficient for larger inputs.
- Dynamic Programming (Memoization) leverages previously computed results to optimize performance.
- Always consider if a problem has an optimal substructure and overlapping subproblems, which are indicators that Dynamic Programming can be applied.
- Memoization is particularly useful when the problem can be broken down into overlapping subproblems that are solved multiple times.
Choosing the right approach not only makes your solution more efficient but also demonstrates a deeper understanding of algorithmic principles, which is crucial in programming and technical interviews.