April 01, 2026 · note
Notes on Algorithm Design
Brief notes on algorithmic paradigms, particularly dynamic programming.
Dynamic programming
Dynamic programming solves problems by breaking them down into simpler overlapping subproblems.
Properties
- Optimal substructure. An optimal solution to the overall problem can be constructed from optimal solutions of its subproblems.
- Overlapping subproblems. The problem can be broken down into subproblems which are reused several times.
Memoization vs. tabulation
- Memoization (top-down). Start solving the given problem by breaking it down. If a subproblem was already computed, return it.
- Tabulation (bottom-up). Start solving the lowest-level subproblem and build up to the main problem.