Guided Notes

Dynamic Programming

Overlapping subproblems and optimal substructure, memoization, tabulation, and the 0/1 knapsack problem.

What is dynamic programming?

Slide 1 / 5

Dynamic 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.

← Maximum Flow