Complexity Analysis
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]What is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(n)
How to derive it
Single loop from 3 to n, each iteration does O(1) work → O(n) time. The dp array has n+1 elements → O(n) space. This could be optimized to O(1) space by keeping only the last two values (like Fibonacci), but the array version is clearer for analysis.