liveBook · Manning

Overlapping subproblem

As explained in Timeless Algorithms, The Foundational Ideas

An overlapping subproblem is a repeated smaller instance generated by the decomposition of a larger computational problem.

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

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines repeated instances and illustrates their reuse across recursive and state-based problems, while treating optimal substructure as a separate requirement.
Examples
Uses Fibonacci recursion, knapsack states, coin-change amounts, inventory states, and intermediate routes.
What you can do after
Evaluate whether repeated instances can be solved once and reused when assessing dynamic-programming suitability.
How it connects
Connects dynamic programming with recursion, optimal substructure, and state-based optimization.

Also explained in

Compare how 2 books explain overlapping subproblem →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.