Dynamic programming — overlapping subproblems, optimal substructure: Visual walkthrough

This is the visual companion to the parent topic. We start from absolute zero: you only need to know what "adding two numbers" means and what a recipe that calls itself is (a quick refresher on Recursion helps).

Step 1 — What "a subproblem" even looks like

WHAT. Our running example is the Fibonacci sequence. It is defined by one rule: $F (n) = F (n - 1) + F (n - 2)$

Let us decode every symbol before we use it:

$F$ is a machine: you feed it a whole number $n$ , it returns one number back.
$n$ is the input — "which Fibonacci number do you want?"
$F (n - 1)$ and $F (n - 2)$ are the two smaller questions the machine must ask to answer the big one. These smaller questions are the subproblems.
The $+$ says: combine the two smaller answers by adding them.

We also need the base cases — the smallest questions the machine can answer instantly without asking anything: $F (0) = 0, F (1) = 1$

WHY define this first. You cannot talk about "repeated work" until you can point at one unit of work — one call to $F$ on one input. That single box is the atom of everything below.

PICTURE. Below, one call is drawn as a box labelled by its input. An arrow means "this box asks that box a question."

Figure — Dynamic programming — overlapping subproblems, optimal substructure

Step 2 — Grow the full recursion tree (watch the waste appear)

WHAT. Take the top question $F (5)$ and keep applying the rule until every branch reaches a base case ( $F (0)$ or $F (1)$ ). Each box sprouts two children: its $F (n - 1)$ and its $F (n - 2)$ .

WHY. We want to count the total work. Total work = total number of boxes in this tree, because each box does one addition. So we must draw the whole thing.

PICTURE. Look at the tree. Now hunt for repeats: how many separate boxes say $F (3)$ ? $F (2)$ ? Colour-coded below — the same question is being re-asked from scratch on different branches. Nobody remembers anything.

Recall Count the repeats yourself

In the $F (5)$ tree: how many times does $F (2)$ get computed? ::: Three separate times. How many times does $F (3)$ get computed? ::: Twice.

Those repeated boxes are exactly the overlapping subproblems the parent note warned about. They are the enemy. (This is unlike Divide and Conquer, where every box is a different question and nothing repeats.)

Step 3 — Measure the waste: why the tree is $O (2^{n})$

WHAT. Count boxes by level (distance from the top).

Level 0: $1$ box ( $F (5)$ ).
Level 1: $2$ boxes.
Level 2: up to $4$ boxes.
Level $k$ : up to $2^{k}$ boxes.

WHY this tool — powers of two. Every box makes two children, so the population doubles each level down. Whenever a quantity doubles at each step, the honest way to describe its size is a power of two, $2^{k}$ . That is precisely why we reach for $2^{n}$ and not, say, $n^{2}$ : doubling is the fingerprint of exponential growth.

Total boxes $\approx 1 + 2 + 4 + \dots + 2^{n} \approx 2^{n + 1}$ , which we write as == $O (2^{n})$ == (the parent's Time Complexity Analysis "big-O" = "grows no faster than").

PICTURE. Each level drawn as a bar; the bar length doubles going down. The total area is the wasted work.

Step 4 — The key observation: how MANY distinct questions exist?

WHAT. The tree has $\sim 2^{n}$ boxes — but list the distinct inputs appearing anywhere in it: $F (0), F (1), F (2), F (3), F (4), F (5)$ That is only 6 different questions for $F (5)$ . In general, for $F (n)$ there are exactly $n + 1$ distinct inputs: $0, 1, 2, \dots, n$ .

WHY this is the whole game. The tree is huge because distinct questions get re-asked. But there are only about $n$ genuinely different questions. If we could answer each different question once and reuse it, our total work would be about $n$ , not $2^{n}$ .

PICTURE. The messy tree on the left is squeezed onto a short number line of the only inputs that truly exist, $0$ through $n$ . Many tree boxes collapse onto the same tick.

Step 5 — Install the sticky-note (memoization) and watch branches die

WHAT. Add a table memo (a shelf of sticky notes indexed by input). New rule for every call:

If the answer for $n$ is already on the shelf, hand it back — do not recurse.
Otherwise compute it once, write it on the shelf, then return it.

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]   # <-- the sticky note: reuse, don't recompute
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Line by line:

if n < 2: return n — base cases $F (0) = 0, F (1) = 1$ , answered instantly.
if n in memo: return memo[n] — the whole point. The second time any question is asked, its entire subtree is skipped.
memo[n] = ... — solve once, record the answer.

WHY. In Step 2 the branches for the second $F (3)$ , the second/third $F (2)$ , etc. were pure repetition. The sticky-note check prunes those repeated branches to a single lookup box. (See Memoization vs Tabulation for the top-down vs bottom-up split.)

PICTURE. The same $F (5)$ tree, but every box after the first time a value is computed is greyed-out and replaced by a one-step lookup. The fat exponential tree deflates into a thin chain.

Step 6 — Count again: the multiplication formula falls out

WHAT. After memoization, each distinct input is computed exactly once. So: $Time = Step 4 (# distinct subproblems) \times one +, i.e. O (1) (work per subproblem)$

Plug Fibonacci in:

$# distinct subproblems = n + 1 \approx n$
work per subproblem $= O (1)$ (one addition + one shelf write)

$Time = n \times O (1) = O (n)$

WHY a product, not a sum? Because the two quantities are independent: how many different jobs there are, times how long each job takes. This is the master formula for every DP — Fibonacci, Knapsack Problem ( $nW$ jobs), Longest Common Subsequence ( $nm$ jobs), even Bellman-Ford ( $V E$ relaxations). Change the two factors, get any DP's cost.

PICTURE. A grid: columns = distinct subproblems, one cell each; a small clock inside each cell = work per cell. Total time = filling every cell once = (columns) × (per-cell work).

Step 7 — The degenerate / edge cases (never skipped)

WHAT & WHY. A derivation is only trustworthy if it survives the extremes.

$n = 0$ or $n = 1$ (base cases). The tree is a single box; there is nothing to overlap. Naive and DP both cost $O (1)$ . Memoization here is neither faster nor slower — just harmless. Lesson: overlap only appears once the tree is deep enough to branch back onto itself.
A problem with NO overlap (e.g. Merge Sort, Divide and Conquer). Every distinct-subproblem count equals the total-box count. The two numbers from Step 4 are the same, so caching saves nothing and only wastes shelf space. DP is pointless here.
A problem with NO optimal substructure (e.g. longest simple path in a graph). Combining sub-answers is illegal because sub-paths can reuse a node the whole path already used — so the shelf stores a value that is wrong to reuse. Here memoization is not just useless, it gives a wrong answer.

PICTURE. Three tiny trees side by side: (a) the flat base case with no repeats, (b) a Merge-Sort tree where all leaves are distinct, (c) a path graph where reusing a sub-answer double-counts a node — marked with a red ✗.

Recall When does the trick actually help?

Caching pays off only when ::: distinct subproblems ≪ total boxes (real overlap) AND sub-answers combine correctly (optimal substructure).

The one-picture summary

Everything above, on a single canvas: the fat $2^{n}$ tree on the left, the sticky-note shelf in the middle collapsing repeats, and the thin $O (n)$ chain on the right — with the master formula printed underneath.

Recall Feynman: tell the whole walkthrough like a story

We started with a machine that answers "what's the $n$ -th Fibonacci number?" by asking two smaller versions of itself. Drawing that out (Step 1–2), we got a bushy tree that doubles at every level, so it has about $2^{n}$ boxes — a mountain of work — and lots of those boxes ask the exact same question (Step 3). Then came the punchline (Step 4): even though there are $2^{n}$ boxes, there are only about $n$ different questions in the whole tree. So we hand the machine a shelf of sticky notes (Step 5): the first time it answers a question it writes the answer down; every later time it just reads the note instead of re-doing the whole subtree. The bushy tree deflates into a thin chain. Counting again (Step 6): each of the $\approx n$ different questions is solved once, each costing one addition, so total time is $n \times 1 = O (n)$ — that's the master DP formula, (number of different jobs) × (time per job). Finally we checked the edges (Step 7): if the tree never repeats itself, or if the sub-answers can't legally be combined, the sticky-note trick either wastes paper or lies to you. That's the whole soul of dynamic programming in one picture.

Connections

Parent topic (Hinglish) — the full treatment.
Recursion — the tree we started from.
Recursion Trees — the counting technique of Steps 2–3.
Memoization vs Tabulation — the shelf, top-down and bottom-up.
Time Complexity Analysis — where $O (2^{n})$ and $O (n)$ come from.
Divide and Conquer — the no-overlap edge case.
Knapsack Problem, Longest Common Subsequence, Bellman-Ford — the same master formula with different job counts.