Dynamic programming starts with a question: if I knew the answers for smaller inputs, could I build the answer for this one? Here the answer is yes, and the naive recursion is so slow that the speed-up is obvious.
You are climbing a staircase with n steps. Each move you can climb either 1 or 2 steps. Return the number of distinct ways to reach the top.
Examples
Input: n = 2
Output: 2
Explanation: 1+1 or 2
Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1
Constraints
1 <= n <= 45- Target: O(n) time, O(1) extra space (plain recursion without memoization is far too slow for n = 45)
Goals
- Write a recurrence: express the answer for n in terms of smaller answers
- Recognise overlapping subproblems and replace exponential recursion with a table or two variables
- Build a bottom-up 1D DP from base cases