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
- memoisation — Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
- tabulation — Bottom-up dynamic programming: filling a table of subproblem answers in order from the base cases up, so each entry's inputs are ready before it.
- optimal substructure — The property that an optimal solution to a problem is built from optimal solutions to its subproblems.
- overlapping subproblems — The property that a recursive solution solves the same subproblems again and again.
- knapsack problem — The problem of choosing items, each with a weight and a value, to maximise total value without exceeding a weight capacity.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers