The same question, asked again and again
A problem has overlapping subproblems when a recursive solution revisits the same subproblem many times instead of always generating fresh ones. This is the second precondition for dynamic programming, alongside optimal substructure.
The classic example
The naive recursive Fibonacci computes the value at n by computing n minus one and n minus two, each of which recomputes smaller values. The same intermediate values are calculated over and over, and the total work grows exponentially even though there are only a linear number of distinct subproblems.
- The recursion tree contains repeated nodes.
- The count of unique subproblems is far smaller than the count of recursive calls.
Turning repetition into speed
When subproblems overlap, you store each subproblem's answer the first time it is computed and reuse it afterward. This collapses the exponential recursion tree into a graph of distinct subproblems. The fix is exactly memoization or tabulation. Contrast this with divide and conquer methods like merge sort, whose subproblems are disjoint and never overlap, so caching would gain nothing.
Key idea
Overlapping subproblems occur when recursion solves the same subproblem repeatedly; storing each distinct answer once turns an exponential recursion into an efficient computation.