Dynamic programming is usually implemented one of two ways: memoization (top-down) or tabulation (bottom-up). Explain both.
Your answer should cover:
- What property a problem needs before DP applies at all (name and explain the two classic conditions).
- How memoization works mechanically, and what it adds to plain recursion.
- How tabulation works mechanically, and how you decide the fill order.
- The practical trade-offs: when would you pick each? (Think: code clarity, stack limits, subproblem coverage, space optimisation.)
- Illustrate with Fibonacci or Climbing Stairs: show how the same recurrence appears in both styles.