Q16: How do you solve Climbing Stairs using Dynamic Programming and Space Optimization?
You are climbing a staircase of $n$ steps. You can climb 1 or 2 steps at a time. Recurrence relation: $dp[i] = dp[i-1] + dp[i-2]$ (Fibonacci pattern). Optimize space to $O(1)$ using two variables (prev1, prev2).
Climbing Stairs Space-Optimized Solution
public class ClimbStairs {
public static int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1, prev1 = 2;
for (int i = 3; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}💡 Computes step combinations iteratively using constant auxiliary space.
Key Takeaways
- Base cases: $dp[1] = 1$, $dp[2] = 2$.
- Space optimized to $O(1)$ variable swaps.
Knowledge Check
What is the time and space complexity of the space-optimized Climbing Stairs algorithm?