Dynamic Programming

Compute Fibonacci numbers with the textbook recursion $F(n) = F(n-1) + F(n-2)$ and count the function calls. For $F(30) = 832{,}040$ the naive code makes 2,692,537 calls, yet there are only 31 distinct inputs, $F(0)$ through $F(30)$. Almost all of the work recomputes answers the program already found. The call count is $2F(n+1) - 1$, which grows like $\varphi^n$ with $\varphi \approx 1.618$, so $F(50)$ this way makes about 41 billion calls and runs for most of an hour in Python.

Two properties make a problem a candidate for dynamic programming. Overlapping subproblems: the recursion asks the same smaller question many times. Optimal substructure: the answer to the big question is built from answers to smaller ones, so solving each subproblem once and storing it is enough.

The fix costs one table. Store each $F(k)$ the first time you compute it, and the whole thing takes $n+1$ evaluations: $O(n)$ time instead of exponential.

You need both properties. Merge sort builds its answer from the answers for two halves, but the halves never share a subproblem, so a cache would never get a hit. The test in an interview is simple: write the recursion, then ask whether the same arguments come up along different branches. If they do, cache them.