Overlapping subproblems occur when solving a larger problem generates the same smaller instances repeatedly. Dynamic programming solves each distinct instance once, stores its result, and reuses it. section 6.1.1
Repeated instances make reuse possible, but do not alone justify dynamic programming: the problem must also have optimal substructure. Without both conditions, the method adds complexity without meaningful advantage. section 6.1.1
The repeated instances take different forms across problems:
- In recursive Fibonacci computation, values such as F4, F3, and F2 recur across branches. section 6.1.1
- In 0/1 knapsack, the same state (i, c)—the first i items and remaining capacity c—can arise along different decision paths. section 6.2.1
- Coin-change paths can reach the same remaining amount; inventory decisions can reach the same period and inventory; and route calculations can reuse the same intermediate routes. section 6.3.1 section 6.4.2 section 6.4.3
Figure 6.1 Recursive computation of the sixth Fibonacci number. Although the recursion tree branches rapidly, many intermediate values are computed repeatedly. These overlapping subproblems make the Fibonacci sequence an ideal candidate for dynamic programming, where each distinct subproblem is solved once and then reused whenever it reappears.

The recursion tree for F6 shows how many branches revisit the same Fibonacci values. section 6.1.1

