Problem Statement
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?
Approach
DP: Ways(n) = Ways(n-1) + Ways(n-2). Base cases: Ways(1)=1, Ways(2)=2. We can optimize space to O(1) by storing only the last two values.
Time & Space Complexity
Time complexity is O(n). Space complexity is O(1).