Climbing Stairs
You are climbing a staircase. It takes n steps to reach to the top. At each step, you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Constraints:
- 1 <= n <= 45
Examples:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top: 1 step + 1 step, or 2 steps.
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top: 1 step + 1 step + 1 step, or 1 step + 2 steps, or 2 steps + 1 step.
Solutions
Dynamic Programming
We use dynamic programming to solve this problem. We create an array dp of size n + 1, where dp[i] represents the number of ways to climb i steps. We initialize dp[1] = 1 and dp[2] = 2, because there is only one way to climb 1 step and two ways to climb 2 steps. Then, for each step from 3 to n, we calculate dp[i] as the sum of dp[i - 1] and dp[i - 2], because we can climb i steps by either climbing 1 step from the (i - 1)th step or 2 steps from the (i - 2)th step.
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3;
i <= n;
i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}Optimized Dynamic Programming
We can optimize the dynamic programming solution by only keeping track of the last two steps, because each step only depends on the previous two steps. We use two variables a and b to keep track of the number of ways to climb the previous two steps, and update them in each iteration.
function climbStairs(n) {
let a = 1,
b = 1;
for (let i = 2; i <= n; i++) {
let temp = a + b;
a = b;
b = temp;
}
return b;
}
Follow-up:
What if we can climb 1, 2, or 3 steps at a time?
