dynamic programming

A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.

In more detail

It applies when a problem has optimal substructure and overlapping subproblems. It can be written top-down with memoisation or bottom-up with tabulation; both give the same answer. Knapsack, longest common subsequence, edit distance and coin change are standard examples, and DP is the safe fallback when greedy fails.

Related terms

Taught in

References