liveBook · Manning

Overlapping subproblem

An overlapping subproblem is a smaller computational problem that recurs during the decomposition of a larger problem.

How 2 Manning books explain it

Algorithms Every Programmer Should Know

An overlapping subproblem is a smaller computational problem that occurs repeatedly within the recursive decomposition of a larger problem.

How it is used
Identifies repeated remaining-capacity calculations that dynamic programming avoids in 0/1 knapsack.
How deep it goes
Works through repeated states and a bottom-up table; does not develop a general test for overlap beyond knapsack.
Examples
Uses four cloud instances under an eight-credit limit and compares inclusion with exclusion in individual table cells.
What you can do after
Build it from scratch using a 2D dynamic-programming table that reuses saved knapsack results.

Read how Algorithms Every Programmer Should Know explains overlapping subproblem →

Timeless Algorithms, The Foundational Ideas

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

How it is used
Tests whether a problem has repeated instances that dynamic programming can reuse.
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.

Read how Timeless Algorithms, The Foundational Ideas explains overlapping subproblem →

Also covered in

Related concepts

Questions about overlapping subproblem

What is overlapping subproblem?

An overlapping subproblem is a smaller computational problem that recurs during the decomposition of a larger problem.

Which Manning books explain overlapping subproblem?

Algorithms Every Programmer Should Know and Timeless Algorithms, The Foundational Ideas.

What is overlapping subproblem a kind of?

Overlapping subproblem is a kind of subproblem. A subproblem is a smaller, well-defined problem derived from a larger problem whose solution contributes to solving the larger problem.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.