Dynamic Programming
Dynamic programming decomposes a problem into overlapping subproblems and stores their solutions to avoid recomputation, solving bottom-up or top-down (memoization).
Purpose
To efficiently solve optimization problems with optimal substructure and overlapping subproblems.
Mechanism
Identify optimal substructure: the optimal solution contains optimal solutions to subproblems. Bottom-up: fill the table in increasing order of size. Top-down: recursion with memoization. Classics: knapsack, longest common subsequence, edit distance, matrix-chain multiplication.
Use cases
- Algorithm design
- Optimization problems
- Sequence analysis