Glossary

Dynamic Programming

Dynamic programming (DP) is an optimisation technique for recursive algorithms: subproblem results are cached to avoid recomputing them. It transforms problems from O(2ⁿ) to O(n) or O(n²).

Two approaches

Top-down (memoisation) — recursion + result cache. More natural to write
Bottom-up (tabulation) — iteratively fill a table from base cases upward

Fibonacci numbers

// Without DP: O(2^n)
fib(n) = fib(n-1) + fib(n-2)

// With memoisation: O(n)
$memo = [];
function fib(int $n): int {
  global $memo;
  if ($n <= 1) return $n;
  return $memo[$n] ??= fib($n-1) + fib($n-2);
}

When to apply

The problem has optimal substructure (the optimal solution is composed of optimal subsolutions) and overlapping subproblems. Classic problems: longest common subsequence, knapsack, shortest path in a graph.