overlapping subproblems
Imagine you are climbing a staircase and someone asks how many ways there are to reach step 10, where each move goes up one or two steps. To answer for step 10 you need the answer for step 9 and step 8. But to answer for step 9 you again need step 8 and step 7. The answer for step 8 keeps coming up again and again from different directions. If you recompute it from scratch every time, you do an enormous amount of duplicated work. That repeated demand for the same small answers is what we call overlapping subproblems.
More precisely, a problem has overlapping subproblems when a plain recursive solution, as it breaks the problem into smaller pieces, ends up solving the same smaller piece many times. The honest test is to draw the recursion tree (the picture of which call makes which calls) and look for the same call appearing in more than one place. For computing the n-th Fibonacci number, fib(n) calls fib(n-1) and fib(n-2); fib(n-1) calls fib(n-2) and fib(n-3); so fib(n-2) is already needed twice, fib(n-3) three times, and the duplication snowballs. The number of distinct subproblems here is only about n (the values fib(0) through fib(n)), yet the naive recursion makes roughly 2^n calls. Almost all of that work is recomputation.
This is exactly the opening that dynamic programming exploits. The key insight is to count the distinct subproblems, not the total recursive calls: if there are only polynomially many different subproblems but exponentially many calls, then computing each distinct subproblem once and storing the answer turns an exponential algorithm into a polynomial one. Note the contrast with divide and conquer such as merge sort, where the subproblems are on disjoint halves and never overlap — there, caching buys you nothing because every call is genuinely new.
Naive fib(5) expands into fib(4)+fib(3); fib(4) into fib(3)+fib(2); so fib(3) is computed twice, fib(2) three times, fib(1) five times. The distinct subproblems are only fib(0)..fib(5) — six of them — yet the tree has 15 calls. For fib(50) the gap is between 51 distinct values and over a billion calls.
Few distinct subproblems but many repeated calls is the hallmark that invites dynamic programming.
Overlapping subproblems alone are not enough; you also need optimal substructure. And recomputation is only wasteful when the same subproblem recurs — merge sort recurses heavily but its subproblems never overlap, so memoizing it gains nothing.