Guided Notes
Dynamic Programming
Overlapping subproblems and optimal substructure, memoization, tabulation, and the 0/1 knapsack problem.
What is dynamic programming?
Slide 1 / 5Dynamic programming (DP) solves a problem by breaking it into smaller subproblems, solving each one once, and reusing the answers.
It applies when a problem has: • Overlapping subproblems — the same smaller problem comes up again and again. • Optimal substructure — the best overall answer is built from best answers to subproblems.
DP routinely turns exponential algorithms into polynomial ones.