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.