Q14: Climbing Stairs (Dynamic Programming)
You are climbing a staircase requiring $n$ steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
DP Climbing Stairs Solution
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1;
let prev1 = 2;
for (let i = 3; i <= n; i++) {
let current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
console.log(climbStairs(5)); // 8💡 To reach step i, you can arrive from step i-1 or step i-2. Summing these options gives total ways, matching Fibonacci transitions.
Key Takeaways
- Follows Fibonacci sequence progression: $dp[i] = dp[i-1] + dp[i-2]$.
- Can be solved in O(n) time and O(1) space using dynamic programming space optimization.
Knowledge Check
What is the space complexity of the variable-tracking dynamic programming approach above?