liveBook · Manning

Overlapping subproblem

As explained in Algorithms Every Programmer Should Know

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

Suppose you have a fixed budget for cloud instances and want the greatest possible throughput. Each instance must be taken whole or left behind. Trying every combination works for a small pool, but with 40 choices it means over a trillion possible paths. Many paths ask the same smaller question: what is the best value available from a particular set of remaining items at a particular remaining capacity? That repeated question is an overlapping subproblem. section 7.0 section 7.1

Dynamic programming answers each such question once and saves the result. In a 0/1 knapsack table, T[i, w] records the best value obtainable from the first i items with capacity w. Fill the zero-item and zero-capacity boundaries with zero. For each other cell, skip the current item if it does not fit; otherwise record the larger of two values: the best value without it, or its value plus the best value for the capacity left after taking it. Both earlier results come from the previous row, so an item cannot be taken twice. section 7.1

Figure 7.3 Visualization of the math used to evaluate cell T[2, 3] (circled in green) on the second row (w2 = 2, v2 = 3). The algorithm resolves a binary choice by executing a maximum value comparison between two paths. The exclusion path inherits the value directly above (T[1, 3] = 2). The active inclusion path accepts the new instance's throughput value (v2 = 3, highlighted in the red solid box) and subtracts its weight from the current capacity (3 - 2 = 1), forcing a pointer lookup to the previous row at column 1 (T[1, 1] = 2, highlighted by the red dotted circle). The combined value of 5 outperforms the exclusion path, updating the cell state.

Follow the two lookups for T[2, 3]: skipping the second item gives 2, while taking it adds 3 to the saved value 2 at T[1, 1]. The cell records 5. section 7.1

An eight-credit budget

Four instances cost 1, 2, 4 and 5 credits and provide values 2, 3, 5 and 6. The table has five rows, including the no-items row, and nine columns for capacities 0 through 8. At its final cell, skipping the five-credit instance gives 10. Taking it gives 6 plus the saved best value of 5 at capacity 3, for an optimum of 11. section 7.1

The tradeoff is storage for fewer repeated calculations. Testing all item combinations grows as O(2ⁿ); filling the table visits one cell per item-and-capacity pair, using a matrix of (n + 1) × (W + 1) cells. Look for overlapping subproblems when different choice paths keep returning to the same smaller state. section 7.0 section 7.1

How Algorithms Every Programmer Should Know covers it

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 it assumes
Starts with binary item choices and teaches the table from its zero boundaries; assumes familiarity with basic loops and arrays for the Python implementation.
What you can do after
Build it from scratch using a 2D dynamic-programming table that reuses saved knapsack results.
How it connects
Connects overlapping subproblems to dynamic programming, 0/1 knapsack, brute-force search and optimal substructure.

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 Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.