In dynamic programming, what does 'overlapping subproblems' mean, and how does naive recursive Fibonacci show it?
answer
- recursion alone is not enough
- same shape, or same arguments?
- count distinct inputs, not calls
- where does FIB(3) appear twice?
- n+1 questions, far more calls
basics
~20 sOverlapping subproblems means the same subproblem instance, with identical arguments, is solved repeatedly. Naive recursive Fibonacci recomputes the same argument in many separate branches, so distinct subproblems number about n while calls grow far faster.
solid answer
~40 sOverlapping subproblems means a recursive formulation keeps hitting the *same* subproblem instance — same arguments, same answer — through different paths of the recursion, so the number of **distinct** subproblems is far smaller than the number of recursive calls. Naive Fibonacci is the standard demonstration: `FIB(5)` needs `FIB(4)` and `FIB(3)`, but `FIB(4)` needs `FIB(3)` again, and that whole recomputation repeats deeper down. The distinct inputs are only the values `0..n`, roughly `n+1` of them, while the naive call count grows exponentially. That gap is exactly what a cache converts into lookups. The key distinction: recursion alone does not imply overlap — a routine that recurses over each node of a tree once has subproblems that are all *different*, so caching them buys nothing.
code
pseudocode · 11 linesFIB(n):
if n <= 1:
return n
return FIB(n-1) + FIB(n-2)
// expanding FIB(5) by hand:
// FIB(5) -> FIB(4) + FIB(3)
// FIB(4) -> FIB(3) + FIB(2) <- FIB(3) asked a second time
// FIB(3) -> FIB(2) + FIB(1) <- and FIB(2) keeps reappearing
// ...
// distinct arguments ever asked: 0..ngo deeper
Be ready to define overlapping subproblems as the same arguments being solved repeatedly, and to walk the first two levels of the Fibonacci expansion out loud showing where a value repeats.
Explain the mechanism: name the parameters of the recursive call, count how many distinct combinations exist, and contrast that count with the number of calls the naive version makes.
Show you use the property as a sizing tool — estimate the state space from the parameters before writing code, and say plainly when a recursion has no overlap and a cache would be dead weight.
Own the framing that overlap is an efficiency property while optimal substructure is a correctness property, and that a team announcing 'this is DP' has argued only half the case until both are stated.
## The property, stated precisely A problem has **overlapping subproblems** when a natural recursive formulation of it solves the *same subproblem instance* — the same arguments, therefore the same answer — many separate times. The emphasis belongs on *instance*. Two subproblems overlap when they are literally the same question, not when they merely have the same shape or the same size. This is one of the two properties a problem needs before dynamic programming is the right tool; the other is optimal substructure. Overlap is the property that makes DP *fast*. Optimal substructure is the property that makes it *correct*. ## The canonical demonstration The recursive definition of the Fibonacci numbers is the demonstration every interviewer reaches for: ``` FIB(n): if n <= 1: return n return FIB(n-1) + FIB(n-2) ``` Expand `FIB(5)` by hand for two levels. It calls `FIB(4)` and `FIB(3)`. `FIB(4)` in turn calls `FIB(3)` and `FIB(2)`. So `FIB(3)` is now being computed twice, in two independent parts of the expansion, with no knowledge of each other — and each of those two computations re-expands the entire subtree beneath it, where `FIB(2)` appears again, and again. Now count the two quantities separately, because conflating them is the mistake this question exists to catch: - **Distinct subproblems:** the argument is a single integer between `0` and `n`, so there are about `n+1` distinct questions the recursion can ever ask. - **Recursive calls:** the naive expansion makes exponentially many, because nothing remembers an answer once it is found. The ratio between those two numbers is the overlap. When it is large, storing each distinct answer the first time it is computed and returning the stored copy afterwards turns almost all of the work into lookups. ## How to test a problem for overlap The practical test in an interview is: **write down the parameters your recursive call takes, and ask how many different combinations of them exist.** That set is the subproblem space. Then ask whether the recursion reaches the same combination through more than one route. If the parameter space is small relative to the branching of the recursion, you have overlap. If every recursive call carries a parameter combination that can only be reached once, you do not. ## The contrast: recursion without overlap Consider a routine that sums the values stored in a rooted tree by recursing into each child and adding the results. It is recursive, it has subproblems ("what is the sum of this subtree?"), and it decomposes cleanly. But each subtree is asked about exactly once, because a node has exactly one parent, so no two calls ever share arguments. Adding a cache keyed by node would produce zero hits and pure overhead. That routine is not a DP candidate no matter how recursive it looks. This is the single most common misunderstanding: treating "it is recursive" or "it breaks into smaller pieces of the same kind" as evidence of overlap. Plenty of recursive algorithms decompose into pieces that never repeat. ## What overlap does and does not promise - It does **not** promise correctness of a DP formulation. A problem can repeat subproblems constantly and still have no valid recurrence, because the optimal answer is not built from optimal sub-answers. - It does **not** promise polynomial time. The payoff from caching is bounded by the *size* of the distinct subproblem space. If that space is itself exponential — for instance because a subproblem must be identified by a set rather than by a number — then caching removes duplicated work and still leaves an exponential amount of distinct work. - It does **not** depend on how the answers are stored. Recording answers on the way down or filling them in a fixed order from the bottom up are two ways of exploiting the same property; the property itself is about the problem, not the storage. ## Saying it well out loud A strong answer names the instance-level identity ("the same arguments, reached by different routes"), quantifies the gap ("about `n` distinct subproblems versus a call tree that blows up"), and volunteers the negative case ("a recursion whose subproblems are all distinct gains nothing from a cache"). That last sentence is what separates a candidate who has memorised a definition from one who can recognise the property in a problem they have not seen.
- If a recursive routine has no repeated subproblem instances, what does adding a cache buy you?Nothing but overhead. Every lookup misses, so you pay for hashing or table allocation and the extra memory while every result is still computed exactly once. Caching converts *repeated* work into lookups; where there is no repetition there is nothing to convert. This is why recognising overlap precedes deciding to memoize.
- Does overlapping subproblems alone make a problem a dynamic programming problem?No. Overlap makes caching *profitable*; it says nothing about whether a recurrence is *valid*. You also need optimal substructure — the guarantee that an optimal solution to the whole is built from optimal solutions to the parts. A problem with heavy overlap but no optimal substructure will produce a fast algorithm that returns wrong answers.
- How do you estimate the subproblem space before writing any code?List the parameters your recursive call would take and multiply out their ranges. Two indices over a sequence of length n give about n^2 states; one index plus a remaining-capacity value gives n times capacity. That product, times the work done per state, is the running time you are signing up for — and it is the number to sanity-check before committing to the approach.
It is the difference between looking up the same phone number twenty times because you never wrote it down, and looking up twenty different numbers. Only the first situation is fixed by a notebook.
saying these in an interview costs you the question
- Says overlapping means the subproblems merely look similar
- Claims every recursive problem has overlapping subproblems
- Counts recursive calls instead of distinct subproblem instances
- Thinks caching helps simply because recursion is slow
- Treats overlap alone as proof that DP applies