Overlapping Subproblems
Overlapping subproblems appear when different recursive paths ask for the same smaller answer, making caching or tabulation dramatically reduce work.
What Overlap Means
A subproblem is one smaller question inside the original problem. Subproblems overlap when the same smaller question is reached through multiple paths. The key word is same: same inputs, same constraints, same required answer. If two calls only look similar but carry different remaining capacity, index, or boundary, they are different states.
Overlap is the reason DP improves on plain recursion. A recursive formulation might be logically correct, but if it recomputes the same state many times, its running time can explode. DP keeps the first result and reuses it.
Fibonacci as the Minimal Example
Naive Fibonacci asks fib(n) to compute fib(n - 1) and fib(n - 2). Those branches immediately collide. For fib(5), the call fib(3) appears on both sides, and fib(2) appears even more often.
This is not a coincidence; every level fans out into calls that share descendants. The recursive tree has exponential size, while the number of distinct states is only n + 1. DP changes the cost from counting calls to counting unique states.
How to Detect It in Interviews
When you write a recurrence, ask whether two different choices can lead to the same remaining problem. If yes, look for overlap. In Coin Change, choosing coin 1 then 2 can reach the same remaining amount as choosing 2 then 1. In House Robber, many take or skip paths ask for the best answer starting at the same index. In Edit Distance, many edit sequences reach the same pair of prefix lengths.
A practical test is to name the state. If the state space is much smaller than the naive recursion tree, DP is likely appropriate. If each subproblem is unique, as in classic binary search or Merge Sort, DP usually gives no benefit.
Overlap Is About Identity, Not Size
Two subproblems overlap only when they are identical under your state definition. For example, ways(i, amount) and ways(i + 1, amount) are not the same even though the amount matches, because the available coins differ. Conversely, if the order of previous choices no longer matters, many histories can collapse into one state.
This is why state design and overlap are connected. A state should keep enough information to be correct, but not extra history that prevents identical futures from merging.
Naive Fibonacci call tree
- fib(5)
- fib(4)
- fib(3)
- fib(2)recomputed later
- fib(1)base
- fib(0)base
- fib(1)base
- fib(2)repeated
- fib(1)base
- fib(0)base
- fib(3)repeated
- fib(2)repeated again
- fib(1)base
- fib(0)base
- fib(1)base
The tree repeats fib(3) and fib(2). Memoization stores each value after the first computation, while tabulation computes each value once in increasing order.
Key Takeaways
- Overlapping subproblems are identical states reached by different choice paths.
- Naive recursion can be exponential even when the number of unique states is only linear or polynomial.
- Naming the state is the fastest way to see whether histories collapse into shared futures.
- If subproblems are independent and never repeat, the problem is more likely divide and conquer than DP.