Dynamic Programming

The name “dynamic programming” is misleading — the technique has little to do with “programming” in any planning sense. It’s closer to decomposition. DP makes a decomposable problem easier to solve; usually the problem already admits a recursive formulation, and DP is the trick of remembering and reusing sub-results.

The knapsack problem

Given a set of items, each with its own weight and price, and a total weight limit, how do you pick items to maximize total price? The name comes from picking the best subset to fit into a knapsack.

Knapsack is a textbook DP example because it phrases as a decision problem: with total weight ≤ W, maximize total value V.

The hard part: each item is either “in” or “out”, and the optimal decision for any one item depends on what you decide for the others. A greedy value-per-weight heuristic doesn’t get you far — you need a global view.

Recursive solution

Direct recursion works. Walk the items, and for each one branch on “include” vs “skip”:

• If item n is included: recurse on weight remaining - weight of n, current value + value of n, items excluding n.
• If item n is skipped: recurse on weight remaining, current value, items excluding n.

Each side-effect-free subproblem is captured by three parameters: remaining weight, current value, available items. Those three fully determine the answer.

The DP version

Turning that recursion into DP is mechanical: as long as subproblems overlap and are side-effect-free, cache the answer to each subproblem and reuse it whenever the same parameters show up again.

So what kinds of problems is DP actually applicable to? Beyond the hand-wavy descriptions, here’s a checklist:

• Structure: subproblems must overlap. That’s what lets a cache reuse them under “same params ⇒ same answer”. Note this doesn’t mean every subproblem looks the same — multiple mutually recursive functions can also be DP’d, as long as the parameter space is enumerable.
• Boundedness: the problem must be bounded. This is really a prerequisite of recursion, not DP. The input has to look like “pick among n items”, not “pick repeatedly without limit”.
• Independence: a subproblem’s answer must depend only on its parameters, not on outside state. Otherwise the cache key isn’t actually a key.