Climbing Stairs
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?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps3. 2 steps + 1 step
Constraints:
1 <= n <= 45
Solve it on LeetCode
Approaches
1. Recursive Solution
The climbing stairs problem can be solved using a recursive approach. The core idea is to think of climbing stairs as making a series of steps. At each step, you have two choices: take one step or take two steps.
Intuition:
- Start from the base step (step 0) and determine how many ways can you reach the top step (step
n). - At each step
i, you have two choices: move toi+1ori+2. - Recursively calculate the number of ways to reach the top from each of these steps.
- The base cases are:
- If you reach step
n, there's 1 way to stay there (do nothing). - If you surpass step
n, there are 0 ways.
Code:
- Time Complexity: O(2^n), because each step splits into two possibilities (recursive calls).
- Space Complexity: O(n), due to the recursion stack depth.
2. Dynamic Programming (Top-Down Memoization)
This approach uses memoization to store results of subproblems, reducing repeated calculations.
Intuition:
- Similar to the recursive approach, but use an array to store already computed results for each step.
- The memoization array
memostores results of the number of ways to climb to the top from each step. - Fill in the memoization table on the fly, storing each result for quick access.
Code:
- Time Complexity: O(n), each step calculation is done once and stored.
- Space Complexity: O(n), due to the memoization array.
3. Dynamic Programming (Bottom-Up)
This approach involves using an iterative dynamic programming approach, filling from the bottom up without recursion.
Intuition:
- Initialize a DP array
dp[]wheredp[i]represents the number of ways to reach stepi. - Start with base conditions
dp[0] = 1anddp[1] = 1. - Iteratively fill the array using the relation
dp[i] = dp[i-1] + dp[i-2].
Code:
- Time Complexity: O(n), each step is calculated once in a loop.
- Space Complexity: O(n), stored in the dp array.
4. Optimized Dynamic Programming (Space-Optimization)
By observing that the DP approach only uses the last two numbers, we can optimize space usage.
Intuition:
- Instead of maintaining the whole DP array, keep only two variables to hold the last two states.
- This reduces space complexity substantially.
Code:
- Time Complexity: O(n), each step is calculated once in a loop.
- Space Complexity: O(1), using constant space for last two computed states.