Dynamic programming

Dynamic programming is a way to solve a problem by breaking it into smaller subproblems, solving each one only once and saving the answer so you never recompute it. It applies when the same subproblems keep coming up (overlapping subproblems) and the best overall answer can be built from the best answers to smaller pieces (optimal substructure). Computing Fibonacci numbers naively repeats the same calls exponentially often, while storing each result makes it a single pass. You can write it top-down, as recursion plus a cache, or bottom-up, by filling a table in order. The hard part is choosing the right definition of a subproblem, the state; after that the code is often short.