Back to 1-D Dynamic Programming
Easy
Climbing Stairs
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?
Examples
Input:n = 2
Output:2
There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Input:n = 3
Output:3
There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints
1 <= n <= 45
Dynamic Programming (Bottom-Up)
Approach
To reach step `i`, you must have come from either step `i-1` or step `i-2`. Therefore, the total number of ways to reach step `i` is the sum of ways to reach step `i-1` and step `i-2`. This is identical to the Fibonacci sequence. We can optimize the space to O(1) by only keeping track of the previous two steps instead of an entire array.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
We only need to iterate from 3 to n, doing constant work at each step. Space is optimized by storing only two variables instead of a DP array of size n.
Solution.java
class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } int prev1 = 1; // Ways to reach step i-2 int prev2 = 2; // Ways to reach step i-1 for (int i = 3; i <= n; i++) { int current = prev1 + prev2; prev1 = prev2; prev2 = current; } return prev2; }}