Exercises — Dynamic programming — overlapping subproblems, optimal substructure

(a) Fibonacci — both. The call tree for $F(n)$ recomputes $F(k)$ for small $k$ enormously many times → overlap. And $F(n)=F(n-1)+F(n-2)$ literally builds the answer from sub-answers → optimal substructure. ✅ DP applies. (b) Merge Sort — optimal substructure only. Sorting the whole is built from sorting each half, so the substructure is there. But the two halves are disjoint index ranges — no subproblem is ever revisited, so there is no overlap. ⇒ This is Divide and Conquer, not DP. Caching would waste memory for zero speedup. (c) Max by scanning — neither (trivially). There is one linear pass; there is no recursion revisiting anything. Nothing to cache.

No. DP needs optimal substructure. For longest simple path it fails: the best path $s\to t$ is not built from an independently-best $s\to m$ plus best $m\to t$, because those pieces might reuse vertices, which "simple" forbids. Sub-answers are not composable, so caching them yields wrong results. (This is exactly the parent note's warning: prove the substructure before you memoize.)

Fill smallest → largest so each entry's dependencies already exist: $0,1,1,2,3,5,8,13$ for indices $\mathrm{0..7}$. So $F(7)=13$. Each cell used only $dp[i-1]+dp[i-2]$ — both already written. That's optimal substructure made concrete.

Rows = items considered $\mathrm{0..4}$, columns = capacity $c=\mathrm{0..5}$. Row $0$ is all zeros (no items). Reading the figure's grid:

Sample cell $K(2,5)$: skip $B$ → $K(1,5)=3$; take $B$ → $4+K(1,5-3)=4+K(1,2)=4+3=7$. Max $=7$. Answer: $7$ (take $A+B$: weight $2+3=5\le 5$, value $3+4=7$). $C,D$ never improve the last column here.

$dp[0]=0$. For $a\ge 1$, $dp[a]=1+{\min }_{\text{coin }k\le a}dp[a-k]$.

• $dp[1]=1+dp[0]=1$
• $dp[2]=1+dp[1]=2$
• $dp[3]=\min (1+dp[2],1+dp[0])=\min (3,1)=1$
• $dp[4]=\min (1+dp[3],1+dp[1],1+dp[0])=\min (2,2,1)=1$
• $dp[5]=\min (1+dp[4],1+dp[2],1+dp[1])=\min (2,3,2)=2$
• $dp[6]=\min (1+dp[5],1+dp[3],1+dp[2])=\min (3,2,3)=2$

Answer: $dp[6]=2$ (coins $3+3$).

Naive: each node spawns two children, and no memory exists, so the tree roughly doubles per level → about $2^n$ nodes, each doing $O(1)$ work ⇒ $O(2^n)$. The figure's left tree shows $F(3)$ appearing twice, $F(2)$ three times — pure repeated work. Memoized: the first time each $F(k)$ is computed it fills the cache; every later request is an $O(1)$ lookup (the greyed nodes in the right tree). There are only $n+1$ distinct values $F(\mathrm{0..}n)$, each computed once ⇒ using the parent's formula $\text{Time}=(\#\text{distinct subproblems})\times (\text{work each})=(n+1)\times O(1)=O(n).$

$O(nW)$ is pseudo-polynomial, not truly polynomial. $W$ is a value, and its size in bits is ${\log }_{2}W$, so the table has $n\cdot W$ cells but the input is only $\sim n\log W$ bits. Here $n\cdot W=5\times 10^{10}$ cells — infeasible, even though $n$ is tiny. Fast in $n$, exponential in the number of bits of $W$. (See Time Complexity Analysis.)

Let $d_k(v)=$ shortest distance to $v$ using at most $k$ edges. Optimal substructure: a shortest $\le k$-edge path to $v$ is a shortest $\le (k-1)$-edge path to some neighbour $u$, plus edge $u\to v$: $d_k(v)=\min (d_{k-1}(v),{\min }_{u\to v}(d_{k-1}(u)+w(u,v)\left)\right).$ A simple shortest path uses at most $V-1$ edges, so after $V-1$ full relaxation rounds every $d_{V-1}(v)$ is final. Each round is one DP layer; overlap is huge because many edges feed the same vertex. That is exactly (#subproblems)$\times$(work) $=O(V)\times O(E)=O(VE)$.

Derivation. Look at the last characters $X_i,Y_j$.

• If $X_i=Y_j$: that char must extend an LCS of the shorter prefixes, so $L(i,j)=1+L(i-1,j-1)$.
• If $X_i\ne Y_j$: at least one of them isn't in the common subsequence, so $L(i,j)=\max (L(i-1,j),L(i,j-1))$.
• Base: $L(0,j)=L(i,0)=0$ (empty prefix).

Optimal substructure: an optimal LCS of the prefixes is composed of an optimal LCS of shorter prefixes (swap-in argument). Overlap: $(i-1,j)$ and $(i,j-1)$ both recurse into $(i-1,j-1)$ — shared subproblems everywhere.

Compute $X=$AGCAT (rows), $Y=$GAC (cols). Table $L$ (rows $i=\mathrm{0..5}$, cols $j=\mathrm{0..3}$):

LCS length $=2$ (e.g. "AC" or "GA").

The last move landed from step $n-1$, $n-2$, or $n-3$. Those are disjoint final moves, so we add the counts: $W(n)=W(n-1)+W(n-2)+W(n-3),W(0)=1,W(1)=1,W(2)=2.$

• $W(3)=1+1+2=4$
• $W(4)=2+4+...=W(3)+W(2)+W(1)=4+2+1=7$
• $W(5)=W(4)+W(3)+W(2)=7+4+2=13$

Answer: $W(5)=13$. Optimal substructure = "any full way ends with exactly one last hop"; overlap = each $W(k)$ reused by three parents.

Each row $i$ reads only row $i-1$. So keep a single 1-D array dp[0..W] and update it in place per item. But $K(i,c)$ needs $K(i-1,c-w_i)$ — an entry to its left and from the old row. If you iterate $c$ upward, you'd overwrite dp[c-w_i] to the new row before reading it (that would let one item be taken twice — the unbounded knapsack). To preserve the old left value for 0/1, iterate $c$ downward from $W$ to $w_i$:

for i in range(n):
    for c in range(W, w[i]-1, -1):
        dp[c] = max(dp[c], v[i] + dp[c-w[i]])

Rule: descend $c$ so each item is used at most once. Same $O(nW)$ time, now $O(W)$ space.

Optimal substructure broke relative to their state. Once "use each element ≤ twice" is added, the answer at index $i$ depends not just on $i$ but on how many times each value was already used — that extra history is part of the true subproblem. Memoizing on $i$ alone merges states that are actually different, so a cached value gets served in a context where it's invalid. Fix: enlarge the state to capture everything the future depends on (here, remaining usage budget), or prove the reduced state is sufficient. A correct memo key must make the subproblem self-contained.

For the fractional version, greedy is optimal and simpler than DP: sort by value/weight ratio and fill. Ratios: $A=3/2=1.5$, $B=4/3\approx 1.33$, $C=5/4=1.25$, $D=6/5=1.2$. Take $A$ fully (uses 2, value 3, left 3), then $B$ fully (uses 3, value 4, left 0). Total weight $=5$, value $=7$. Here it ties the 0/1 answer, but in general fractional greedy $\ge$ 0/1 DP. Lesson: DP is not always the right hammer — when the greedy-choice property holds, greedy is both correct and cheaper.

Which property makes DP correct, and which makes it worth it? Correct ::: Optimal substructure (sub-answers compose into the true optimum). Worth it ::: Overlapping subproblems (the same sub-answer is reused, so caching saves work).