Dynamic Programming
- Definition
- Dynamic Programming (DP) solves complex problems by breaking them into overlapping subproblems and reusing solved sub-results (memoization). It turns exponential problems into polynomial-time ones when overlapping structure exists. Think of computing Fibonacci numbers once and saving them instead of recalculating. DP differs from greedy or divide-and-conquer methods by exploiting repeated subproblems and optimal substructure; it's deterministic and exact when applicable.
How does it work?
Dynamic programming solves problems by computing and reusing solutions to overlapping subproblems. Implementations are either memoized recursion or iterative table filling; identify state variables and transitions, and ensure an ordering that respects dependencies to compute bottom-up.
Examples
- Sequence alignment — Compute optimal alignments in bioinformatics (Needleman–Wunsch) using DP matrices.
- Knapsack and resource allocation — Exact DP solutions for constrained optimisation over item choices.
- Optimal control (discrete) — Bellman backups for finite-horizon decision processes and value iteration.
Problems
- Exponential memory use when the state space is large
- Identifying correct overlapping subproblems and recurrence relations
- Doesn't apply cleanly to problems lacking optimal substructure
- Off-by-one and boundary condition bugs in table initialization