Dynamic Programming
DP is a well-known and very common approach to solving
optimization problems. What is it? What are some examples?
What Is It?
First, some things to know:
- The name is kind of, but not totally,
just made up.
- It's a way to solve problems that have
optimal substructure AND overlapping subproblems,
while not repating work in the overlapping parts (“subproblems + reuse” — Erik Demaine).
- Top-down approach involves recursion, memoization, and guessing.
- Bottom-up approach is a topological sort on the subproblem dependency DAG
(so it's not going to work if the subproblem dependencies are cyclic).
- Commonly used in optimization.
- When solving subproblems, try them all, but choose the best one.
A Brief History
Top-Down vs. Bottom-Up Approaches
Examples
Interval scheduling
Longest common subsequence
Coin changing
Levenshtein distance
Matrix-chain multiplication
Integer 0/1 knapsack
Integer
0/1 Knapsack using Dynamic Programming
Shortest path
Bellman-Ford
Algorithm
Word wrap
Word
Wrap Dynamic Programming
Traveling salesperson
TSP Dynamic
Programming