= Overlapping subproblems
{wiki}
<Overlapping subproblems> occur when several parts of a calculation request the same smaller problem. <Memoization> can share its answer if the <memoization key> identifies that problem completely. For the <Fibonacci numbers>, both $F_5$ and $F_4$ require $F_3$. In <dynamic programming>, the <dynamic programming state> plays the corresponding role of identifying a reusable continuation. Overlap explains potential savings; the <recurrence relation> and its base cases still need to be correct.
Back to article page
