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).
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.
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.
When To Use It
Look for overlapping subproblems when a brute-force or recursive solution repeats the same calculation with the same inputs.