Dynamic programming solves complex problems by decomposing them into recursive subproblems, solving each subproblem once, storing its result, and combining those results into the final solution. section 1.3.3
The technique is especially useful when:
- Subproblems recur during the computation, making repeated solution work avoidable through stored results. section 1.3.3
- A difficult optimization problem can be replaced by a pseudo-polynomial algorithm whose running time depends on an input value such as capacity. section 1.3.3
- Requirements and constraints can be examined before committing to an algorithm, since relaxing a constraint may produce a cheaper solution. section 1.3.5
0-1 knapsack
For a crate with capacity 1000 kg and 62 items, dynamic programming considers capacity values and items, taking about 1000 × 62 steps instead of exploring roughly 2^62 combinations. This is practical because the bounded capacity makes the pseudo-polynomial approach fast. section 1.3.3
