Climbing Stairs
LeetCode #70 · Easy · Dynamic Programming · C++ solution with worked-out approach and complexity analysis.
Approach
Dynamic Programming (Fibonacci Sequence)
Key insight
To reach step i, you could have come from: 1. Step i-1 (by taking 1 step) 2. Step i-2 (by taking 2 steps) Therefore, the total number of ways to reach step i is the sum of ways to reach step i-1 and step i-2 (fibonacci sequence). This forms the recurrence relation: ways(i) = ways(i-1) + ways(i-2)
Strategy
- 1Base cases:
- 2For n >= 4, use the recurrence relation to build up the solution.
- 3Use a vector to store the results (memoization/tabulation).
Time
O(n)
one pass to calculate up to n
Space
O(n)
to store the ways for each step
Problem description(from LeetCode)
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
Example 1
- Input:
- n = 2
- Output:
- 2
- Note:
- There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps 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 steps 3. 2 steps + 1 step
Constraints
- •1 <= n <= 45
C++ Solution
solution.cpp
class Solution {
public:
int climbStairs(int n) {
if (n < 4) return n;
vector<int> s(n + 1);
s[1] = 1;
s[2] = 2;
for (int i = 3; i <= n; i++) {
s[i] = s[i - 1] + s[i - 2];
}
return s[n];
}
};