Dynamic Programming

• Used with problems that have:

  • Optimal substructure

  • Overlapping subproblems

• Bottom-up: iterative (tabulation), top-down: recursive (memoization)

• We need base cases, a recurrence relation for state transisition, and a function or data structure to compute/contain answers for any given state.