DP problems — rod cutting, egg drop, DP on trees: Worked examples

Definition Two names we use throughout (defined before any use)

Rod: $r (n)$ = the best (maximum) revenue obtainable from a rod of length $n$ .
Egg — the drop function: $D (e, f)$ = the minimum number of drops in the WORST case that guarantees you find the threshold floor, given $e$ eggs and $f$ floors. "Worst case" means: an adversary decides break/survive to make you work hardest, and we still want the fewest drops.
Egg — the forward reach function: $F (e, d)$ = the largest number of floors you can fully resolve using exactly $e$ eggs and a budget of $d$ drops.
Tree (MWIS) — two states per node $v$ :
- $f_{1} (v)$ = best total weight in $v$ 's subtree when $v$ IS chosen.
- $f_{0} (v)$ = best total weight in $v$ 's subtree when $v$ is NOT chosen.

These four names are the entire vocabulary of this page. Every worked line below only ever uses them.

The scenario matrix

Every DP problem in this chapter is a table of subproblems. A "case class" is a region of that table that behaves differently. Here is every region we must cover:

#	Case class	What breaks / is special	Covered by
A	Degenerate input — size 0	The base case; recursion must stop here	Ex 1
B	Rod: normal max	Loop over every leftmost cut	Ex 2
C	Rod: "no cut is best"	Optimum = sell whole rod, all cuts lose	Ex 3
D	Egg: 1 egg (linear floor)	No gambling allowed — forced scan	Ex 4
E	Egg: enough eggs (≈ binary search limit)	Eggs plentiful → answer drops to $⌈ lo g_{2} ⌉$	Ex 5
F	Egg: scarce eggs (2 eggs)	The real "worst-case" trade-off	Ex 6
G	Tree: leaf / single node	Base of the DFS; $f_{1} = w, f_{0} = 0$	Ex 7
H	Tree: include-vs-exclude conflict	Heavy child forces a real choice	Ex 8
I	Greedy trap (word problem)	Greedy loses, DP wins — the star tree	Ex 9
J	Exam twist — negative weights flip "always include?"	Signs change the instinct	Ex 10

We hit all ten cells with ten examples below. (Cell J appears exactly once, in Ex 10. The rod-cutting "sell-whole" surprise below is part of case C, not a separate twist.)

Group 1 — Rod Cutting cases (A, B, C)

Worked example

Ex 1 — Cell A: the empty rod ( $n = 0$ ) Rod of length $0$ , any price array. What is $r (0)$ ?

Forecast: guess the revenue before reading on. Zero? Something? Undefined?

Read the recurrence's boundary. $r (n) = max_{1 \leq i \leq n} (p [i] + r (n - i))$ . For $n = 0$ the range $1 \leq i \leq 0$ is empty — there is no valid $i$ to loop over. Why this step? A max over an empty set has no natural value, so we must define it. This is exactly what a base case is for (see Recursion and Memoization): the place recursion stops instead of looping forever.
Set $r (0) = 0$ . Zero-length rod → nothing to sell → revenue $0$ . Why this step? If we returned $- \infty$ here, every full solution would inherit $- \infty$ and break. $0$ is the identity for addition, so it plugs harmlessly into $p [i] + r (0)$ .

Verify: $r (1) = p [1] + r (0) = p [1] + 0 = p [1]$ . A length-1 rod is worth exactly its price — sanity holds. ✓

Worked example

Ex 2 — Cell B: normal maximisation $p = [_, 1, 5, 8, 9, 10, 17, 17, 20]$ (index 0 unused), $n = 8$ . Find $r (8)$ .

Forecast: the whole rod sells for $p [8] = 20$ . Can cutting beat $20$ ?

Build $r$ bottom-up using $r [j] = max_{1 \leq i \leq j} (p [i] + r [j - i])$ . Why this step? Bottom-up means every $r [j - i]$ we need is already computed — no recomputation, the core DP win.
Fill the table:
- $r [1] = 1$
- $r [2] = max (1 + 1, 5) = 5$
- $r [3] = max (1 + 5, 5 + 1, 8) = 8$
- $r [4] = max (1 + 8, 5 + 5, 8 + 1, 9) = 10$
- $r [5] = max (1 + 10, 5 + 8, 8 + 5, 9 + 1, 10) = 13$
- $r [6] = max (1 + 13, 5 + 10, 8 + 8, 9 + 5, 10 + 1, 17) = 17$
- $r [7] = max (1 + 17, 5 + 13, 8 + 10, 9 + 8, 10 + 5, 17 + 1, 17) = 18$
- $r [8] = max (1 + 18, 5 + 17, 8 + 13, 9 + 10, 10 + 8, 17 + 5, 17 + 1, 20) = 22$ Why this step? Each line tries every leftmost piece $i$ and adds the already-solved rest $r [j - i]$ — that's the optimal substructure in action.
Read off $r [8] = 22$ , achieved by $i = 2$ (price 5) $+ r [6] = 17$ .

Verify: the whole rod gives only $20 < 22$ , so cutting genuinely helps. Reconstruct: cut 2 → then $r [6] = 17$ came from $i = 6$ (whole), so pieces ${2, 6}$ , revenue $5 + 17 = 22$ . ✓

Worked example

Ex 3 — Cell C: no cut is best (and the "sell-whole" surprise) Two sub-parts of the same case class C — where the loop's max lands on an "extreme" option.

Part (i) — many small pieces win. $p = [_, 2, 3, 4]$ , $n = 3$ .

Forecast: prices grow slower than length (price-per-unit falls). Guess: sell whole?

$r [1] = 2$ .
$r [2] = max (2 + 2, 3) = 4$ — two singles beat one double ( $4 > 3$ ). Why this step? Here per-unit price is decreasing, so more small pieces = more money; DP discovers this without us telling it.
$r [3] = max (p [1] + r [2], p [2] + r [1], p [3] + r [0]) = max (2 + 4, 3 + 2, 4 + 0) = max (6, 5, 4) = 6$ . Why this step? The whole rod ( $4$ ) is the worst option; three length-1 pieces win at $6$ .

Verify (i): three unit pieces = $3 \times 2 = 6 = r [3]$ . ✓

Part (ii) — the whole rod wins ("no cut is best"). $p = [_, 1, 20]$ , $n = 2$ .

Forecast: $p [2] = 20$ is huge relative to $p [1] = 1$ . Guess: don't cut.

$r [1] = 1$ .
$r [2] = max (p [1] + r [1], p [2] + r [0]) = max (1 + 1, 20 + 0) = max (2, 20) = 20$ . Why this step? When the whole-rod price dominates, the term $p [n] + r [0]$ wins. DP's max handles "don't cut" as just another candidate ( $i = n$ ) — no special case needed.

Verify (ii): cutting gives $2$ , whole gives $20$ ; $20 > 2$ , so no cut. ✓ Both parts show the same recurrence quietly choosing whichever extreme is optimal.

Group 2 — Egg Drop cases (D, E, F)

Worked example

Ex 5 — Cell E: eggs plentiful (binary-search limit) $e = 10$ eggs, $f = 8$ floors. Find $D (10, 8)$ .

Forecast: so many eggs you can afford to break several. Does the answer fall to $lo g_{2}$ ?

Use the forward "reach" recurrence from the parent: $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1$ , and then apply the bridge $D (e, f) = min {d : F (e, d) \geq f}$ . So find the smallest $d$ with $F (10, d) \geq 8$ . Why this step? With eggs $\geq d$ , breaking is never the bottleneck, so $F$ grows like $2^{d} - 1$ — pure Binary Search behaviour.
With $e \geq d$ every $F (e - 1, d - 1)$ term is "full", giving $F (d, d) = 2^{d} - 1$ . We need $2^{d} - 1 \geq 8 \Rightarrow 2^{d} \geq 9 \Rightarrow d = 4$ (since $2^{3} - 1 = 7 < 8 \leq 15 = 2^{4} - 1$ ). Why this step? $d = 3$ clears only 7 floors, one short; $d = 4$ clears 15, comfortably covering 8.
So by the bridge, $D (10, 8) = 4$ .

Verify: $⌈ lo g_{2} (8 + 1)⌉ = ⌈ lo g_{2} 9 ⌉ = 4$ . Plentiful eggs ⇒ pure binary search ⇒ 4 drops. ✓

Worked example

Ex 6 — Cell F: scarce eggs (2 eggs, 10 floors) $e = 2$ , $f = 10$ . Find $D (2, 10)$ . The parent claimed 4; let's derive it and see the strategy.

Forecast: two eggs, ten floors. More than $lo g_{2} 10 = 4$ ? Exactly 4? Look at the figure's staircase first.

Forward recurrence again: $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ with $F (1, k) = k$ , then use the bridge $D (2, 10) = min {d : F (2, d) \geq 10}$ . Why this step? $F (2, d)$ tells us the tallest building 2 eggs can clear in $d$ drops. The first $d$ whose reach hits $10$ is $D (2, 10)$ .
Compute:
- $F (2, 1) = F (1, 0) + F (2, 0) + 1 = 0 + 0 + 1 = 1$
- $F (2, 2) = F (1, 1) + F (2, 1) + 1 = 1 + 1 + 1 = 3$
- $F (2, 3) = F (1, 2) + F (2, 2) + 1 = 2 + 3 + 1 = 6$
- $F (2, 4) = F (1, 3) + F (2, 3) + 1 = 3 + 6 + 1 = 10$ Why this step? Each first drop with 2 eggs either breaks (leaving 1 egg, $d - 1$ drops) or survives (2 eggs, $d - 1$ drops); the "+1" is this drop.
$F (2, 4) = 10 \geq 10$ , and $F (2, 3) = 6 < 10$ , so by the bridge $D (2, 10) = 4$ . Why this step? First $d$ whose reach covers all 10 floors.
The strategy the figure shows: first drop at floor $4$ (= $F (2, 3) + 1$ ), then $4 + 3 = 7$ , then $7 + 2 = 9$ , then $10$ — the decreasing steps $4, 3, 2, 1$ . Each break shrinks the linear scan below.

Verify: table-DP for $D (2, 10)$ also returns $4$ ; and the steps $4 + 3 + 2 + 1 = 10$ exactly tile the floors. ✓

Group 3 — DP on Trees cases (G, H, I, J)

Worked example

Ex 8 — Cell H: genuine include-vs-exclude conflict Path graph $0 - 1 - 2$ (a line), weights $w_{0} = 4, w_{1} = 10, w_{2} = 4$ , rooted at $0$ .

Forecast: the middle node is heavy ( $10$ ). Take it and lose both ends, or take both ends?

Post-order: process leaf $2$ first: $f_{1} (2) = 4, f_{0} (2) = 0$ . Why this step? DFS forces children before parents so the parent's sums are ready.
Node $1$ (child $2$ ): $f_{1} (1) = w_{1} + f_{0} (2) = 10 + 0 = 10$ ; $f_{0} (1) = max (f_{1} (2), f_{0} (2)) = max (4, 0) = 4$ . Why this step? Including $1$ forbids $2$ (adjacent), so we add $f_{0} (2)$ . Excluding $1$ frees $2$ to be picked → take its best.
Node $0$ (child $1$ ): $f_{1} (0) = w_{0} + f_{0} (1) = 4 + 4 = 8$ ; $f_{0} (0) = max (f_{1} (1), f_{0} (1)) = max (10, 4) = 10$ . Why this step? Including $0$ forbids $1$ , so we chain $f_{0} (1) = 4$ . Excluding $0$ lets $1$ 's best flow up.
Answer $= max (f_{1} (0), f_{0} (0)) = max (8, 10) = 10$ .

Verify: the only sets are ${1} = 10$ vs ${0, 2} = 8$ . DP picks $10$ — the heavy middle beats both ends here. ✓

Worked example

Ex 9 — Cell I: the greedy trap (word problem) A company org-chart is a star: a boss (weight $10$ ) with four direct reports (weight $4$ each). You may invite people to a party, but no manager and their direct report both (awkward). Maximise total "fun weight".

Forecast: greedy grabs the boss (biggest, $10$ ). Is that optimal? Guess before computing.

Greedy attempt (Greedy Algorithms): take boss $= 10$ ; now all four reports are blocked. Total $= 10$ . Why this step? To show greedy's answer so we can beat it.
DP — leaves first: each report $c$ is a leaf: $f_{1} (c) = 4, f_{0} (c) = 0$ .
Root (boss $b$ ):
- $f_{1} (b) = w_{b} + \sum_{c} f_{0} (c) = 10 + 4 \times 0 = 10$ .
- $f_{0} (b) = \sum_{c} max (f_{1} (c), f_{0} (c)) = 4 \times max (4, 0) = 16$ . Why this step? Excluding the boss frees all four reports; $4 \times 4 = 16$ .
Answer $= max (10, 16) = 16$ .

Verify: invite the four reports (no two are adjacent — they only connect through the boss), total $16 > 10$ . Greedy loses by 6. This is exactly why Greedy Algorithms fail on MWIS and DP is needed. ✓

Worked example

Ex 10 — Cell J: the exam twist (negative weights) Same path $0 - 1 - 2$ but weights $w_{0} = 5, w_{1} = - 3, w_{2} = 5$ . Should we ever include a negative node?

Forecast: node $1$ hurts your score. Does DP still consider taking it? Guess the answer.

Leaf $2$ : $f_{1} (2) = 5, f_{0} (2) = 0$ .
Node $1$ : $f_{1} (1) = - 3 + f_{0} (2) = - 3 + 0 = - 3$ ; $f_{0} (1) = max (5, 0) = 5$ . Why this step? Including a negative node gives negative value — DP keeps it as a candidate but it will lose.
Node $0$ : $f_{1} (0) = 5 + f_{0} (1) = 5 + 5 = 10$ ; $f_{0} (0) = max (f_{1} (1), f_{0} (1)) = max (- 3, 5) = 5$ . Why this step? Including $0$ forbids $1$ , but we still add $f_{0} (1) = 5$ (which itself grabbed node $2$ ). This lets us keep both positive ends.
Answer $= max (10, 5) = 10$ , set ${0, 2}$ .

Verify: ${0, 2} = 5 + 5 = 10$ ; including the $- 3$ node never helps. Because MWIS maximises, negative nodes are silently dropped — but note: if the problem forced connectivity you'd have to include it. Here it's free to skip. ✓

Recall Quick self-test

Empty rod value ::: $r (0) = 0$ (max over empty set defined as $0$ ). Why can't 1-egg use binary search? ::: A broken egg is gone; you can't back up, so you must scan linearly, cost $f$ . Bridge from $F$ to $D$ ::: $D (e, f) = min {d : F (e, d) \geq f}$ — fewest drops = first budget whose reach covers $f$ . $F (2, d)$ recurrence ::: $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ ; first $d$ with $F \geq f$ is the answer. Leaf node states in MWIS ::: $f_{1} = w_{v}, f_{0} = 0$ (empty child-sum is 0). Why greedy fails on the star tree ::: Boss (10) blocks four reports; excluding boss yields $4 \times 4 = 16 > 10$ .