Dynamic Programming
Overlapping subproblems, optimal substructure, memoization and tabulation.
Solve a problem by defining subproblems whose answers are reused, so exponential recursion collapses to polynomial time.
Write the natural recursion, then cache every result by its arguments so each distinct subproblem is computed once.
Fill a table of subproblem answers in an explicit order from base cases upward, with loops instead of recursion.
State is a single index into a sequence; dp[i] is the best answer for the prefix (or suffix) ending at i.
State is a pair of prefix lengths (i, j) over two sequences; dp[i][j] combines answers for shorter prefixes of each.
State is (position, small status flag); transitions are the edges of a tiny automaton evaluated once per input element.
State is a cell (r, c); the answer for a cell comes from its allowed predecessor cells (usually up and left).
State is (items considered, capacity used); choose items to maximize value or count/decide subsets hitting a target sum.
State is "best subsequence ending at index i"; transition scans all earlier j that can precede i.
State is a contiguous range [l, r]; the answer is built by choosing a split point or the last element removed inside the range.
State is a node (plus a small flag); each node combines the answers of its children in post-order.
State is a bitmask encoding which of n ≤ ~20 elements are used, plus optionally the last element; transitions add one bit.
Count numbers in [0, N] with a digit property by scanning N's digits with a "tight" flag and a small property state.
State is a vertex; process vertices in topological order so every predecessor is finalized before its successors.
Compute F(n) = F(n-1) + F(n-2) in linear time by reusing the two previous values instead of recomputing them.
Count the ways to reach step n taking 1 or 2 steps at a time — a Fibonacci recurrence in disguise.
Choose a subset of items, each used at most once, maximizing total value without exceeding a weight capacity.
Maximize value under a capacity when every item may be taken any number of times — the 0/1 loop run forward.
Find the fewest coins that sum to an amount (or count the ways) using unlimited coins of given denominations.
Find the length of the longest strictly increasing subsequence — O(n²) DP or O(n log n) with patience sorting.
Find the longest subsequence shared by two sequences using a 2D table over prefix pairs.
Minimum number of insertions, deletions, and substitutions to turn one string into another via a 2D prefix table.
Choose the parenthesization of a matrix product that minimizes scalar multiplications — the archetypal interval DP.
Find the maximum-sum contiguous subarray in one pass by tracking the best sum ending at each position.
Maximize the sum of chosen array elements with no two adjacent — a take-or-skip 1D DP with two rolling variables.