Dynamic programming
Also called: DP
Solving a problem by combining answers to smaller, overlapping subproblems, each computed only once.
Definition
Dynamic programming applies when a problem breaks into smaller versions of itself that repeat. You define a state (what a subproblem is), a transition (how a state follows from smaller ones, usually by asking what the last decision was), base cases and an order, then compute each state once, either top-down with memoization or bottom-up by filling a table.
In practice
The fewest coins for an amount equals one coin plus the fewest coins for the amount minus that coin, minimized over all coins.