Dynamic programming — overlapping subproblems, optimal substructure: Question bank

Two words you'll need constantly:

Subproblem — a smaller version of the same question (e.g. $F (3)$ is a subproblem of $F (5)$ ).
Recurrence — the formula that expresses a big answer in terms of smaller answers.

Both properties, restated in one breath: overlapping subproblems means "the same small question is asked more than once"; optimal substructure means "the best big answer is built from best small answers."

True or false — justify

Every recursive function benefits from memoization.

False — memoization only helps when subproblems overlap; Merge Sort's subproblems are all distinct, so a cache adds memory and saves nothing.

If a problem has optimal substructure, it automatically has overlapping subproblems.

False — they are independent. Binary search on a sorted array has optimal substructure (the answer lives in one recursively-searched half) but each half is a fresh, non-repeating subproblem, so no overlap.

If a problem has overlapping subproblems, DP will always give the correct answer.

False — overlap only makes caching worth it; without optimal substructure the cached sub-answers don't combine into a correct whole (see: longest simple path).

Tabulation and memoization always have the same time complexity.

True in the big-O sense — both solve each distinct subproblem once, so both hit

(# subproblems) \times (work each)

; they differ in constants and recursion overhead, not asymptotics.

Memoization can be asymptotically slower than tabulation for the same problem.

False for time — both are

(# distinct subproblems) \times (work)

. Memoization can add call-stack overhead (a constant factor), and tabulation may waste time on subproblems memoization would skip, but the big-O ceiling is identical.

DP always uses less memory than plain recursion.

False — DP adds a table. It trades memory for time; on a problem with no overlap it spends memory and buys nothing.

The number of distinct subproblems, not the number of recursive calls, sets the DP time.

True — the table guarantees each distinct subproblem is computed exactly once, so distinct-subproblem count (times work each) is the whole cost. See Time Complexity Analysis.

Bottom-up tabulation removes the need to think about the recurrence.

False — the recurrence is the fill rule; tabulation just evaluates it in a dependency-respecting order instead of via recursion.

Greedy and DP solve the same class of problems.

False — Greedy needs the stronger greedy-choice property (one locally-best choice is provably globally safe); DP needs only optimal substructure, which is weaker and covers strictly more problems. See Greedy Algorithms.

Spot the error

"0/1 Knapsack: just sort items by value-to-weight ratio and grab the best until full."

That's the fractional knapsack greedy; for 0/1 you can't split an item, so a high-ratio item can block a better whole-item combination — it can give a wrong total.

"My tabulation reads dp[i-1][c] but I loop i from n down to 1."

Wrong fill order — row

i - 1

must be filled before row

i

is read, so i must increase (or the whole dependency direction must be respected). See Memoization vs Tabulation.

"Longest simple path between two nodes: I'll just memoize on the endpoint pair like shortest path."

No optimal substructure — a longest sub-path may want to reuse a node the outer path already used, so combining sub-answers can produce an invalid (node-repeating) path and a wrong length.

"Fibonacci with def fib(n, memo={}) — the mutable default is a clean private cache."

Trap: the dict is created once and shared across every top-level call, so state leaks between calls. Correct behavior for pure Fib, but a common bug source; prefer passing the memo explicitly or using None.

"Knapsack base case: I left dp[0][c] uninitialized because zero items obviously give zero."

The value is zero, but if the array isn't initialized to

0

the very first row read (dp[i-1] at

i = 1

) is garbage — the base case must be materialized, not merely "obvious."

"I memoized on (i) alone in knapsack to save memory, since c is derivable."

Wrong key — the same item index

i

is reached with different remaining capacities

c

; dropping

c

collapses distinct subproblems and corrupts answers. The state is the full

(i, c)

pair.

"My recurrence is right, so any loop order that fills the whole table works."

False — a correct recurrence still requires reads to happen after their dependencies are written; order is a separate correctness condition from the formula itself.

Why questions

Why must you verify optimal substructure before trusting a DP answer?

Because without it, combining optimal sub-answers can be invalid or suboptimal, so the algorithm returns a confidently wrong number — the code runs fine and lies.

Why does Fibonacci drop from

O (2^{n})

O (n)

under DP?

The naive tree has

\approx 2^{n}

nodes because each call re-spawns work with no memory; caching collapses it to

n

distinct subproblems each done once. See Recursion Trees.

Why is Merge Sort not dynamic programming even though it's recursive?

Its subproblems (the two halves) never repeat — they're disjoint — so there is nothing to cache; DP requires overlap to pay off.

Why does knapsack's time depend on

W

(capacity) and not just

n

(item count)?

The subproblem state is the pair

(i, c)

with

c

ranging

0.. W

, giving

n \cdot W

distinct states — capacity is a genuine dimension of the problem, so it enters the cost.

Why can Bellman-Ford compute shortest paths but not longest simple paths with the same idea?

Shortest paths have optimal substructure (a shortest path's pieces are shortest); longest simple paths do not, because sub-paths can't freely reuse nodes, so the sub-answers don't compose.

Why does memoization solve fewer subproblems than tabulation on some inputs?

Memoization is lazy — it only expands states the top query actually reaches; tabulation eagerly fills the whole table, including states no query needs.

Why is "DP = recursion + remembering" not the whole story?

Remembering only helps if the same questions recur (overlap) and only stays correct if answers compose (optimal substructure); miss either and remembering is useless or wrong.

Edge cases

What does the knapsack recurrence do when an item's weight exceeds remaining capacity (

w_{i} > c

It falls to the "skip" branch

K (i - 1, c)

— the item simply can't be taken, so its value option is never considered.

What is

F (0)

and

F (1)

, and why must both be seeded before the loop starts?

F (0) = 0

F (1) = 1

; the recurrence reads two prior terms, so a single base case leaves the first real step with a missing operand.

In tabulation, what happens if capacity

W = 0

in knapsack?

Every

d p [i] [0] = 0

— no room means no items — and the loops still run harmlessly, returning

0

; the degenerate case is handled by the base row/column, not a special branch.

What if a DP problem has exactly one subproblem depth (no recursion needed)?

Then there's no overlap and nothing to build up — it's a direct computation, and wrapping it in a DP table is pure overhead.

What happens to memoization's benefit as overlap approaches zero (all subproblems distinct)?

The cache never scores a hit, so runtime matches plain recursion while memory grows — the classic "why is my memoized Divide and Conquer not faster?" trap.

For very large

n

, why can Fibonacci tabulation be reduced to

O (1)

space?

Each term needs only the previous two, so you can keep two rolling variables instead of the full array — the table's width, not its history, is what you actually depend on.