Dynamic programming
Also known as: DP, Memoization
Dynamic programming solves problems with overlapping subproblems and optimal substructure by storing each subproblem’s answer once. Top-down form is recursion with memoization; bottom-up form fills a table in dependency order (often a DAG of states).
State definition is the hard part: what is enough to continue optimally? Classic patterns: knapsack, LCS, edit distance, grid paths, interval DP, tree DP, Floyd-Warshall, Bellman-Ford.
Versus divide and conquer: DP reuses overlapping answers. Versus greedy: DP considers multiple candidates per state when a single local choice is not enough.