Overlapping subproblems occur when the same smaller problem appears more than once while solving a larger problem.
This is the main reason dynamic programming can save work.
Core Idea
If a recursive solution keeps asking for the same answer again, the repeated subproblem can be stored and reused. Without overlap, storing previous answers may add complexity without much benefit.
Fibonacci numbers are the classic small example because fib(5) and fib(4) both need fib(3).
The important word is “same.” A subproblem overlaps only when the algorithm reaches the same state again, not merely when it reaches a similar-looking piece of work.
Function Contract
fib_slow(n) expects a non-negative integer and returns the nth Fibonacci number.
The function is intentionally slow because it recomputes the same states many times. It exists to reveal overlapping subproblems, not as the recommended implementation.
Python Example
def fib_slow(n):
if n <= 1:
return n
return fib_slow(n - 1) + fib_slow(n - 2)This recomputes many smaller Fibonacci values. The repeated calls are overlapping subproblems.
Call Tree Example
For fib_slow(5), the recursive calls include:
fib(5)
fib(4) + fib(3)
fib(3) + fib(2) + fib(2) + fib(1)fib(3) appears more than once, and fib(2) appears even more often. Each call with the same n has the same answer, so storing it is safe.
How To Recognize It
Look for a recursive or brute-force solution where different paths ask the same question.
In a grid path-counting problem, the number of ways to reach cell (r, c) may be needed by several later cells. In a knapsack problem, the best value for (item_index, capacity) may be reached through different earlier choices.
If each subproblem is independent and appears only once, the problem may be divide and conquer rather than dynamic programming.
Why Reuse Is Safe
Reuse is safe only when the same state always has the same answer. If solve(i) means the answer from position i onward, then every call to solve(i) can reuse one stored value.
If hidden information changes the answer, the state is incomplete. For example, solve(i) may be insufficient if the answer also depends on remaining capacity, previous choice, or visited nodes. The state may need to become solve(i, capacity) or something larger.
Common Confusions
Smaller subproblems alone are not enough. Divide and conquer also has smaller subproblems, but they are often independent.
Dynamic programming becomes useful when the same state can be reached through different paths or recursive calls.
Caching by the wrong key can hide or create overlap incorrectly. The cache key must represent the full state needed to answer the subproblem.
When To Use It
Look for overlapping subproblems when a brute-force or recursive solution repeats the same calculation with the same inputs.
Once overlap is found, the next question is what state identifies one repeated subproblem.
The Main Point
Overlapping subproblems mean the same state is solved more than once. DP starts by naming that repeated state.