DP problems — rod cutting, egg drop, DP on trees: Exercises

This page is a self-test. Read the problem, try it yourself, then open the collapsible solution. Every problem builds on the parent note and the core idea of Dynamic Programming: find the recursive structure, then stop recomputing it.

Every recurrence here rests on three prerequisites you should keep open: Recursion and Memoization (why solving once and storing wins), Tree Traversal (DFS) (the order we visit tree nodes), and Binary Search (which shows up as a wrong shortcut and a right optimization).

Level 1 — Recognition

Exercise 1.1 — Name the subproblem

Recall Solution

This is pure pattern recognition — no arithmetic.

(a) a shorter rod. We cut once at the left, earn $p [i]$ , and are left with a rod of length $n - i$ — the same problem, smaller input.
(b) a smaller (eggs, floors) pair. After one drop, either the egg broke (fewer eggs, fewer floors below) or survived (same eggs, fewer floors above). Either way the state $(e, f)$ shrinks.
(c) a subtree. Because a tree has no cycles, each child's subtree is a self-contained problem whose answer we combine at the parent.

The single unifying sentence: "What is the smallest set of subproblems whose answers, combined, give the answer to the whole?"

Exercise 1.2 — Read the base case

Recall Solution

$D (5, 0) = 0$ . With zero floors there is nothing to test — the threshold question is already answered, so we make zero drops. (Number of eggs is irrelevant when there is no floor.)
$D (1, f) = f$ . With a single egg, a break is permanent loss of information. If you gamble and drop from floor $k > 1$ and it breaks, you cannot test floors $1.. k - 1$ anymore. So the only safe strategy is to climb floor by floor from the bottom, worst case $f$ drops.

Level 2 — Application

Exercise 2.1 — Turn the rod-cutting crank

Recall Solution

WHAT we do: fill the table left to right, each entry trying every leftmost piece length $i$ .

$j$	computation	$r [j]$	first cut $i$
0	—	0	—
1	$p [1] + r [0] = 2$	2	1
2	$max (p [1] + r [1], p [2] + r [0]) = max (4, 5)$	5	2
3	$max (2 + 5, 5 + 2, 7 + 0) = max (7, 7, 7)$	7	1
4	$max (2 + 7, 5 + 5, 7 + 2, 8 + 0) = max (9, 10, 9, 8)$	10	2

WHY $j = 4$ lands on 10: taking leftmost piece $i = 2$ (price 5) leaves a length-2 rod worth $r [2] = 5$ , total $10$ — beating selling whole at $8$ .

Reconstruct: first cut at $j = 4$ is $i = 2$ → piece of length 2. Remaining rod length $4 - 2 = 2$ ; first cut at $j = 2$ is $i = 2$ → another length-2 piece. Pieces $= {2, 2}$ , revenue $5 + 5 = 10$ .

Exercise 2.2 — Turn the tree crank

Recall Solution

WHAT we do: process leaves first (post-order DFS), because a parent needs its children's answers.

Node 3 (leaf): $f 1 = w_{3} = 1$ , $f 0 = 0$ .
Node 2 (child 3): $f 1 = w_{2} + f 0 [3] = 5 + 0 = 5$ . $f 0 = max (f 1 [3], f 0 [3]) = max (1, 0) = 1$ .
Node 1 (child 2): $f 1 = w_{1} + f 0 [2] = 2 + 1 = 3$ . $f 0 = max (f 1 [2], f 0 [2]) = max (5, 1) = 5$ .
Node 0 (child 1): $f 1 = w_{0} + f 0 [1] = 3 + 5 = 8$ . $f 0 = max (f 1 [1], f 0 [1]) = max (3, 5) = 5$ .

Answer $= max (f 1 [0], f 0 [0]) = max (8, 5) = 8$ .

WHY 8: excluding node 0 (state $f 0 [0] = 5$ ) lets node 1's subtree do its best (which was to exclude 1 and grab node 2). Including node 0 forces excluding node 1, but node 2 is now free — set ${0, 2}$ with weight $3 + 5 = 8$ wins.

Level 3 — Analysis

Exercise 3.1 — Compare choices in egg drop

Recall Solution

For each candidate first-drop floor $x$ , the two branches are: break → $D (1, x - 1) = x - 1$ , survive → $D (2, 6 - x)$ . We take their $max$ (adversary), add 1, then pick the $x$ giving the smallest total.

$x$	break $= x - 1$	survive $= D (2, 6 - x)$	$max$	$1 + max$
1	0	$D (2, 5) = 3$	3	4
2	1	$D (2, 4) = 3$	3	4
3	2	$D (2, 3) = 2$	2	3
4	3	$D (2, 2) = 2$	3	4
5	4	$D (2, 1) = 1$	4	5
6	5	$D (2, 0) = 0$	5	6

The minimum is at $x = 3$ : $D (2, 6) = 3$ , optimal first drop from floor 3.

WHY $x = 3$ balances the two branches best: a good first drop equalizes "cost if it breaks" and "cost if it survives". At $x = 3$ both branches cost $2$ , so neither the break nor the survive case can be worse than the other — the adversary has no lever to pull.

Exercise 3.2 — Reconstruct the rod cut path

Recall Solution

Reconstruction walks the cut array like a linked list:

At length $4$ : $cut [4] = 2$ → emit a piece of length $2$ . Remaining $= 4 - 2 = 2$ .
At length $2$ : $cut [2] = 2$ → emit a piece of length $2$ . Remaining $= 2 - 2 = 0$ .
Length $0$ → stop.

Pieces $= {2, 2}$ , revenue $p [2] + p [2] = 5 + 5 = 10$ . This matches $r [4]$ , confirming the reconstruction.

Level 4 — Synthesis

Exercise 4.1 — Invent a recurrence: rod cutting with a per-cut cost

Recall Solution

WHAT changes: charging a cut whenever we split. Model it by paying $c$ each time we take a leftmost piece and there is a rod left over.

Let $g (j)$ = best net revenue for length $j$ . Trying leftmost length $i$ :

if $i = j$ we sell the whole thing, no cut: value $p [j]$ ;
if $i < j$ we make one cut (fee $c$ ) and continue: value $p [i] - c + g (j - i)$ .

$g (0) = 0, g (j) = max (p [j], max_{1 \leq i < j} (p [i] - c + g (j - i))) .$

Apply ( $c = 1$ ):

$g (1) = p [1] = 1$ .
$g (2) = max (p [2], p [1] - 1 + g [1]) = max (5, 1 - 1 + 1) = max (5, 1) = 5$ .
$g (3) = max (p [3], p [1] - 1 + g [2], p [2] - 1 + g [1]) = max (8, 5, 5) = 8$ .
$g (4) = max (p [4], p [1] - 1 + g [3], p [2] - 1 + g [2], p [3] - 1 + g [1]) = max (9, 8, 8, 8) = 9$ .

WHY the answer dropped from 10 to 9: the old winner ${2, 2}$ earned $10$ gross but needs one cut, netting $10 - 1 = 9$ — now merely tied with selling the whole rod at $9$ (no cut). The cut fee erased the advantage of splitting.

Exercise 4.2 — Invent states: tree with "at most one child kept"

Recall Solution

WHAT constraint we face: unlike MWIS (no adjacent pair), here a picked parent is allowed one picked child. So the parent's value depends on how many children it "spends" its allowance on.

Define two states per node $v$ :

$g (v, 0)$ = best in subtree of $v$ with $v$ not picked — children unconstrained.
$g (v, 1)$ = best in subtree of $v$ with $v$ picked — at most one child may also be picked.

$v$ not picked: every child chooses its own best, no coupling: $g (v, 0) = \sum_{c} max (g (c, 0), g (c, 1)) .$

$v$ picked: the default is each child takes $g (c, 0)$ (not picked). But we're allowed to "upgrade" one child to picked. Upgrading child $c$ gains $g (c, 1) - g (c, 0)$ if that's positive. Pick the single most profitable upgrade:

g(v,1)=\text{base}+\max\Big(0,\ \max_{c}\big(g(c,1)-g(c,0)\big)\Big).$$ Answer $=\max\big(g(\text{root},0),\,g(\text{root},1)\big)$; still $O(n)$ since each edge is touched once. WHY correct: subtrees are disjoint so values add; the only coupling is the "one upgrade" allowance, captured by choosing the best single child gain.

Level 5 — Mastery

Exercise 5.1 — The dual "forward" egg-drop and a complexity claim

Recall Solution

WHAT the dual says: instead of "min drops for $f$ floors", ask "with $d$ drops, how many floors can I clear?" Grow $d$ until $F (2, d) \geq 100$ .

For $2$ eggs, $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ and $F (1, k) = k$ (one egg clears $k$ floors in $k$ drops). This telescopes to the triangular numbers $F (2, d) = \frac{d ( d + 1 )}{2}$ .

$d$	$F (2, d) = d (d + 1) /2$
12	78
13	91
14	105 ≥ 100 ✓

Smallest $d$ with $F (2, d) \geq 100$ is $d = 14$ .

WHY it's faster: the naive table fills $O (e \cdot f)$ cells, each doing an $O (f)$ inner $min_{x}$ scan → $O (e \cdot f^{2})$ . The forward version fills an $e \times d$ table with $O (1)$ per cell, and $d$ is only $O (f)$ for small $e$ — here $d \leq 14$ versus $f = 100$ . So we do $\approx 2 \times 14$ constant-time steps instead of $\approx 2 \times 10 0^{2}$ .

Exercise 5.2 — Why greedy fails on a star, exactly

Recall Solution

(a) Greedy: takes the centre (weight $10$ , the single heaviest). The centre is adjacent to all leaves, so every leaf is now forbidden. Greedy total $= 10$ .

(b) DP optimum via the two MWIS states, root = centre:

Each leaf $ℓ$ : $f 1 [ℓ] = 4$ , $f 0 [ℓ] = 0$ .
Centre included: $f 1 = 10 + \sum f 0 [ℓ] = 10 + 0 = 10$ .
Centre excluded: $f 0 = \sum max (f 1 [ℓ], f 0 [ℓ]) = 4 \times max (4, 0) = 16$ .
Answer $= max (10, 16) = 16$ → set = the four leaves.

(c) When greedy loses: whenever a heavy node's neighbours collectively out-weigh it. Formally, picking node $v$ is a mistake if $w_{v} < \sum_{c \in N (v)} (their achievable contribution when v is excluded)$ . Greedy is locally right ( $10 > 4$ per node) but globally wrong ( $10 < 16$ ). The two-state DP compares include-vs-exclude across the whole subtree at once, so it never falls for this. This is the same reason Greedy Algorithms fail on the Knapsack Problem: a locally best pick can block a globally better combination.

Recall Self-check: match problem → state definition

Rod cutting state ::: $r [j]$ = best revenue from a rod of length $j$ (one dimension). Egg drop state ::: $D (e, f)$ = min worst-case drops with $e$ eggs, $f$ floors (two dimensions). Tree MWIS states ::: $f (v, 0)$ and $f (v, 1)$ = best subtree weight with $v$ excluded / included. Egg drop dual ::: $F (e, d)$ = max floors clearable with $e$ eggs and $d$ drops.