What Are Overlapping Subproblems? The DP Concept Behind Every Cache
- Overlapping subproblems occur when the same recursive call with the same inputs appears at multiple nodes in the recursion tree, making naive recursion exponentially slow
- Naive Fibonacci is O(2^n) because fib(3) gets recomputed hundreds of times; memoization drops it to O(n) by caching each unique result once
- DAG vs tree: the actual dependency structure is a DAG, but naive recursion traverses it as a tree, creating all the redundant work
- Two conditions for DP: overlapping subproblems plus optimal substructure — both must hold before the approach applies
- Recognition signals: small parameter set (polynomial state space), count/min/max objective, or any small recursion tree that shows a repeated node
- Interview arc: write brute-force recursion, identify overlap by tracing a small example out loud, add memoization, re-analyze complexity
Run the naive Fibonacci function for n = 40. On most machines, you'll wait a few seconds. At n = 50, you'll wait minutes. At n = 60, just go home. The function is five lines. The math is addition. Nothing about it looks slow.
The problem is that it recomputes the same values repeatedly, and overlapping subproblems are the name for exactly that phenomenon.
This is one of two conditions that determine whether dynamic programming will help. Get comfortable recognizing it and you'll know, before writing a single line of DP, whether the approach is even worth reaching for.
The Recursion That Repeats Itself
Start with the canonical example:
def fib(n: int) -> int: if n <= 1: return n return fib(n - 1) + fib(n - 2)
Trace what happens when you call fib(5):
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2) → fib(1), fib(0)
│ │ └── fib(1)
│ └── fib(2)
│ ├── fib(1)
│ └── fib(0)
└── fib(3)
├── fib(2) → fib(1), fib(0)
└── fib(1)
fib(3) appears twice. fib(2) appears three times. fib(1) appears five times. Five times, for a value that never changes. By n = 30, you're making roughly 2.7 million calls. By n = 40, over 330 million.
The function isn't slow because Fibonacci is hard. It's slow because the recursion tree is enormous and most of its nodes are doing work someone already did three steps ago. This is what overlapping subproblems means: the same subproblem, with the same inputs, appears at multiple nodes in the recursion tree.
The DAG You're Running as a Tree
A subproblem is a smaller instance of the original problem called during recursion. "Overlapping" means the same subproblem appears at more than one node.
Not all recursive problems have this property. Merge sort splits an array into disjoint halves and never processes the same element twice. Those subproblems don't overlap, which is why memoizing merge sort does nothing.
Fibonacci subproblems are not disjoint. fib(3) is a dependency of both fib(4) and fib(5). Sketch the actual dependency structure and you get a DAG: many paths converge on the same node. But naive recursion treats it as a tree, traversing every path to every node independently. That's where the exponential blowup comes from. You're not discovering new structure at each node. You're re-running paths you've already walked.
Left: fib(4) as a recursion tree. Amber nodes are redundant. Right: the actual DAG, where each value is solved once and referenced many times.
Why the Call Count Explodes
The recurrence for naive Fibonacci is T(n) = T(n-1) + T(n-2) + O(1), which solves to roughly O(φ^n) where φ ≈ 1.618, commonly written as O(2^n). Here's what that looks like as a table of escalating regret:
| n | Approximate function calls |
|---|---|
| 10 | ~177 |
| 20 | ~21,891 |
| 30 | ~2,692,537 |
| 40 | ~331,160,281 |
| 50 | ~40,730,022,147 |
Don't run fib(50). Work roughly doubles with every increment of n. Most of it is redundant. The function is pure (same inputs always return the same output), so every repeated call is strictly wasted work. For more on reading these recurrences, see recursion time complexity.
The Fix: Compute Each Subproblem Once
Since fib(3) always returns the same result, compute it once and store it. Every subsequent call is just a lookup.
from functools import lru_cache @lru_cache(maxsize=None) def fib(n: int) -> int: if n <= 1: return n return fib(n - 1) + fib(n - 2)
The first call to fib(3) computes and caches the answer. Every later call is a dictionary lookup. Time drops from O(2^n) to O(n), and space for the cache is O(n). The recursion tree is still a tree in shape, but you short-circuit every branch the moment you've seen its root. One decorator fixed something that was making your laptop beg for mercy.
This is memoization: top-down DP with a cache. You can also flip to bottom-up, computing values in order from the base cases up:
def fib(n: int) -> int: if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
Both approaches solve the overlapping subproblems problem. The difference is execution order, not insight. The insight is recognizing the overlap in the first place.
This Is Not the Same as Optimal Substructure
Dynamic programming requires two conditions. Overlapping subproblems is one. The other is optimal substructure: the optimal solution to the full problem can be built from optimal solutions to its subproblems.
Both must be present. Running BFS twice on the same graph technically revisits the same computation, but there's no optimal value to carry over, so memoizing it buys you nothing. What triggers the DP approach is the combination: overlapping subproblems plus a "find the minimum, maximum, or count all" objective where you can build the answer from sub-answers.
Check both conditions on a small example before committing to the approach.
Coin Change Shows the Same Structure
The coin change problem has the same shape in a less obvious context. Given coins [1, 5, 10] and a target amount, find the minimum number of coins needed:
def min_coins(coins: list[int], amount: int) -> int: if amount == 0: return 0 if amount < 0: return float('inf') return 1 + min(min_coins(coins, amount - c) for c in coins)
For amount = 11, you might compute min_coins(6) by subtracting 5 from 11, and also compute min_coins(6) by subtracting 1 from 7, and also via a different earlier path. Same subproblem, multiple appearances. A DAG presented as a tree.
Memoizing this drops time from exponential to O(amount × len(coins)). The cache key is amount, and there are only amount + 1 distinct keys. Regardless of how many paths reach min_coins(6), you compute it once.
How to Spot Overlapping Subproblems Before Writing Code
In an interview, you can recognize overlapping subproblems without drawing the full call tree. Look for these signals:
The problem asks for a count, minimum, or maximum across all possible choices. Phrasing like "how many ways can you..." and "what's the fewest steps to..." suggests you're aggregating over branches, which means those branches likely converge.
The recursive state is a small set of parameters. If your function signature is solve(i, remaining) or solve(i, j), there are only i × remaining or i × j distinct subproblems. Exponential branching into a polynomial state space means branches must overlap.
Drawing a small recursion tree reveals duplicates. For n = 5 or amount = 6, writing out the tree takes under two minutes. This is unglamorous and it works every time. If f(3) appears twice, you have overlapping subproblems.
What doesn't indicate overlap: divide-and-conquer on non-overlapping pieces. Binary search discards half the space at each step and never revisits it. Merge sort processes disjoint subarrays. Neither creates repeated calls. For more on distinguishing the patterns, see how to recognize dynamic programming problems.
Why This Matters in Your Interview
The arc of a strong DP interview answer is: write the brute-force recursion, identify overlapping subproblems by tracing a small example out loud, add memoization or convert to tabulation, analyze the new complexity. Each step signals something different to the interviewer.
Identifying overlapping subproblems is the pivot. Without it, you write correct O(2^n) code and have nowhere to go. With it, the fix is mechanical. The interviewer isn't watching to see if you magically know the DP formulation. They want to see you look at your own recursion tree, spot f(3) computed twice, and say: wait, I'm repeating myself.
That reasoning process is hard to practice silently at a keyboard. SpaceComplexity runs live mock interviews where you work through exactly this arc in real time, with rubric-based feedback on whether you caught the DP opportunity, explained your reasoning, and recovered cleanly when the brute-force hit its limits.