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

3.7.14 · D3 · Coding › Algorithm Paradigms › DP problems — rod cutting, egg drop, DP on trees

Definition Do naam jo hum poori tarah use karte hain (kisi bhi use se pehle define kiye gaye)

Rod: $r (n)$ = length $n$ ke rod se milne wala best (maximum) revenue.
Egg — drop function: $D (e, f)$ = worst case mein minimum number of drops jo guarantee karte hain ki aap threshold floor dhundh loge, given $e$ eggs aur $f$ floors. "Worst case" matlab: ek adversary decide karta hai break/survive, taaki aapko sabse zyada kaam karna pade, aur hum phir bhi fewest drops chahte hain.
Egg — forward reach function: $F (e, d)$ = sabse bade number of floors jo aap exactly $e$ eggs aur $d$ drops ke budget se fully resolve kar sakte ho.
Tree (MWIS) — har node $v$ ke liye do states:
- $f_{1} (v)$ = $v$ ke subtree mein best total weight jab $v$ chosen IS.
- $f_{0} (v)$ = $v$ ke subtree mein best total weight jab $v$ chosen NAHI hai.

Yeh chaar naam is page ki puri vocabulary hain. Neeche har worked line sirf inhi ko use karti hai.

Scenario matrix

Is chapter ka har DP problem ek subproblems ka table hai. Ek "case class" us table ka ek region hai jo alag behave karta hai. Yahan har region hai jo hume cover karna hai:

#	Case class	Kya alag hai / special hai	Covered by
A	Degenerate input — size 0	Base case; recursion yahan rukti hai	Ex 1
B	Rod: normal max	Har leftmost cut pe loop	Ex 2
C	Rod: "no cut is best"	Optimum = poora rod becho, sab cuts lose karte hain	Ex 3
D	Egg: 1 egg (linear floor)	Gambling allowed nahi — forced scan	Ex 4
E	Egg: enough eggs (≈ binary search limit)	Eggs plentiful → answer $⌈ lo g_{2} ⌉$ tak girta hai	Ex 5
F	Egg: scarce eggs (2 eggs)	Asli "worst-case" trade-off	Ex 6
G	Tree: leaf / single node	DFS ka base; $f_{1} = w, f_{0} = 0$	Ex 7
H	Tree: include-vs-exclude conflict	Heavy child ek real choice force karta hai	Ex 8
I	Greedy trap (word problem)	Greedy haarta hai, DP jeeта hai — star tree	Ex 9
J	Exam twist — negative weights "always include?" wali instinct badal dete hain	Signs instinct badal dete hain	Ex 10

Hum neeche das examples se saare das cells ko hit karte hain. (Cell J exactly ek baar aata hai, Ex 10 mein. Rod-cutting "sell-whole" surprise neeche case C ka hissa hai, alag twist nahi.)

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

Worked example

Ex 1 — Cell A: empty rod ( $n = 0$ ) Length $0$ ka rod, koi bhi price array. $r (0)$ kya hai?

Forecast: aage padhne se pehle revenue guess karo. Zero? Kuch? Undefined?

Recurrence ki boundary padho. $r (n) = max_{1 \leq i \leq n} (p [i] + r (n - i))$ . $n = 0$ ke liye range $1 \leq i \leq 0$ empty hai — loop karne ke liye koi valid $i$ nahi hai. Yeh step kyun? Empty set pe max ki koi natural value nahi hoti, isliye hume ise define karna hoga. Yahi ek base case ka kaam hai (dekho Recursion and Memoization): woh jagah jahan recursion forever loop karne ki bajay rukti hai.
$r (0) = 0$ set karo. Zero-length rod → kuch bechna nahi → revenue $0$ . Yeh step kyun? Agar hum yahan $- \infty$ return karte, toh har full solution $- \infty$ inherit karta aur toot jaata. $0$ addition ka identity hai, isliye yeh $p [i] + r (0)$ mein harmlessly plug ho jaata hai.

Verify: $r (1) = p [1] + r (0) = p [1] + 0 = p [1]$ . Length-1 rod exactly apni price ke barabar hai — sanity holds. ✓

Worked example

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

Forecast: poora rod $p [8] = 20$ mein bikta hai. Kya cutting $20$ se zyada de sakta hai?

$r$ ko bottom-up build karo $r [j] = max_{1 \leq i \leq j} (p [i] + r [j - i])$ use karke. Yeh step kyun? Bottom-up matlab har $r [j - i]$ jo hume chahiye woh already computed hai — no recomputation, yahi DP ki core jeet hai.
Table fill karo:
- $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$ Yeh step kyun? Har line har leftmost piece $i$ try karti hai aur already-solved rest $r [j - i]$ add karti hai — yahi optimal substructure action mein hai.
$r [8] = 22$ read off karo, jo $i = 2$ (price 5) $+ r [6] = 17$ se milta hai.

Verify: poora rod sirf $20 < 22$ deta hai, isliye cutting actually help karta hai. Reconstruct: cut 2 → phir $r [6] = 17$ $i = 6$ (whole) se aaya, toh pieces ${2, 6}$ , revenue $5 + 17 = 22$ . ✓

Worked example

Ex 3 — Cell C: no cut is best (aur "sell-whole" surprise) Same case class C ke do sub-parts — jahan loop ka max ek "extreme" option pe land karta hai.

Part (i) — bahut saare chhote pieces jeette hain. $p = [_, 2, 3, 4]$ , $n = 3$ .

Forecast: prices length se slower badhti hain (price-per-unit girta hai). Guess: poora becho?

$r [1] = 2$ .
$r [2] = max (2 + 2, 3) = 4$ — do singles ek double se behtar hain ( $4 > 3$ ). Yeh step kyun? Yahan per-unit price decrease ho raha hai, isliye zyada chhote pieces = zyada paisa; DP yeh bina bataye discover karta hai.
$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$ . Yeh step kyun? Poora rod ( $4$ ) sabse bura option hai; teen length-1 pieces $6$ pe jeet jaate hain.

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

Part (ii) — poora rod jeetta hai ("no cut is best"). $p = [_, 1, 20]$ , $n = 2$ .

Forecast: $p [2] = 20$ $p [1] = 1$ ke relative bahut bada hai. Guess: mat kato.

$r [1] = 1$ .
$r [2] = max (p [1] + r [1], p [2] + r [0]) = max (1 + 1, 20 + 0) = max (2, 20) = 20$ . Yeh step kyun? Jab whole-rod price dominate karti hai, toh term $p [n] + r [0]$ jeetta hai. DP ka max "don't cut" ko sirf ek aur candidate ( $i = n$ ) ke roop mein handle karta hai — koi special case nahi chahiye.

Verify (ii): cutting $2$ deta hai, whole $20$ deta hai; $20 > 2$ , toh no cut. ✓ Dono parts dikhate hain ki same recurrence quietly jo bhi extreme optimal hai use choose kar leta hai.

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

Worked example

Ex 4 — Cell D: one egg (forced linear scan) $e = 1$ egg, $f = 6$ floors. $D (1, 6)$ find karo (minimum worst-case drops).

Forecast: ek fragile egg ke saath, kya aap binary-search kar sakte ho? Number guess karo.

Base case apply karo $D (1, f) = f$ . Yeh step kyun? Ek egg ke saath aap use oopar risk nahi kar sakte — agar yeh floor $x$ pe toot jaata hai toh aapke paas koi egg nahi bachta aur floors $1.. x - 1$ unknown rehte hain. Isliye aapko $1, 2, 3, \dots$ climb karke har floor test karna hi padega.
Isliye $D (1, 6) = 6$ . Yeh step kyun? Worst case = threshold sabse oopar hai → aap saari 6 floors ek-ek karke test karte ho.

Verify: Binary Search se contrast karo jo $⌈ lo g_{2} 6 ⌉ = 3$ claim karta. Yeh yahan galat hai kyunki binary search failed probe ke baad free "back-up" assume karta hai; tuta hua egg woh deny karta hai. $D (1, 6) = 6$ . ✓

Worked example

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

Forecast: itne zyada eggs ki aap kaafi toad sakte ho. Kya answer $lo g_{2}$ tak girta hai?

Parent se forward "reach" recurrence use karo: $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1$ , aur phir bridge $D (e, f) = min {d : F (e, d) \geq f}$ apply karo. Toh sabse chhota $d$ dhundho jisme $F (10, d) \geq 8$ ho. Yeh step kyun? Jab eggs $\geq d$ ho, breaking kabhi bottleneck nahi hoti, isliye $F$ $2^{d} - 1$ ki tarah badhta hai — pure Binary Search behaviour.
$e \geq d$ ke saath har $F (e - 1, d - 1)$ term "full" hoti hai, giving $F (d, d) = 2^{d} - 1$ . Hume chahiye $2^{d} - 1 \geq 8 \Rightarrow 2^{d} \geq 9 \Rightarrow d = 4$ (kyunki $2^{3} - 1 = 7 < 8 \leq 15 = 2^{4} - 1$ ). Yeh step kyun? $d = 3$ sirf 7 floors clear karta hai, ek kam; $d = 4$ 15 clear karta hai, 8 easily cover karta hai.
Toh bridge se, $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$ . $D (2, 10)$ find karo. Parent ne 4 claim kiya; aao ise derive karte hain aur strategy dekhte hain.

Forecast: do eggs, das floors. $lo g_{2} 10 = 4$ se zyada? Exactly 4? Pehle figure ka staircase dekho.

Forward recurrence again: $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ with $F (1, k) = k$ , phir bridge $D (2, 10) = min {d : F (2, d) \geq 10}$ use karo. Yeh step kyun? $F (2, d)$ batata hai ki 2 eggs $d$ drops mein sabse lamba building clear kar sakti hain. Pehla $d$ jiska reach $10$ tak pahunche wahi $D (2, 10)$ hai.
Compute karo:
- $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$ Yeh step kyun? 2 eggs ke saath har pehla drop ya toh toot jaata hai (1 egg bachta hai, $d - 1$ drops) ya survive karta hai (2 eggs, $d - 1$ drops); "+1" yahi drop hai.
$F (2, 4) = 10 \geq 10$ , aur $F (2, 3) = 6 < 10$ , toh bridge se $D (2, 10) = 4$ . Yeh step kyun? Pehla $d$ jiska reach saare 10 floors cover kare.
Figure jo strategy dikhata hai: pehla drop floor $4$ pe (= $F (2, 3) + 1$ ), phir $4 + 3 = 7$ , phir $7 + 2 = 9$ , phir $10$ — decreasing steps $4, 3, 2, 1$ . Har break neeche linear scan ko chhota karta hai.

Verify: $D (2, 10)$ ke liye table-DP bhi $4$ return karta hai; aur steps $4 + 3 + 2 + 1 = 10$ exactly floors tile karte hain. ✓

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$ (ek line), weights $w_{0} = 4, w_{1} = 10, w_{2} = 4$ , rooted at $0$ .

Forecast: middle node heavy hai ( $10$ ). Ise lo aur dono ends khao, ya dono ends lo?

Post-order: pehle leaf $2$ process karo: $f_{1} (2) = 4, f_{0} (2) = 0$ . Yeh step kyun? DFS parents se pehle children force karta hai taaki parent ke sums ready hon.
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$ . Yeh step kyun? $1$ ko include karna $2$ ko forbid karta hai (adjacent), isliye hum $f_{0} (2)$ add karte hain. $1$ ko exclude karna $2$ ko pick hone deta hai → uska best lo.
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$ . Yeh step kyun? $0$ ko include karna $1$ ko forbid karta hai, isliye hum $f_{0} (1) = 4$ chain karte hain. $0$ ko exclude karna $1$ ka best flow up karne deta hai.
Answer $= max (f_{1} (0), f_{0} (0)) = max (8, 10) = 10$ .

Verify: sirf sets hain ${1} = 10$ vs ${0, 2} = 8$ . DP $10$ pick karta hai — heavy middle yahan dono ends se jeetta hai. ✓

Worked example

Ex 9 — Cell I: greedy trap (word problem) Ek company org-chart ek star hai: ek boss (weight $10$ ) with chaar direct reports (weight $4$ each). Aap log ko ek party mein invite kar sakte ho, lekin koi manager aur unka direct report dono nahi (awkward hoga). Total "fun weight" maximise karo.

Forecast: greedy boss ko grab karta hai (sabse bada, $10$ ). Kya yeh optimal hai? Compute karne se pehle guess karo.

Greedy attempt (Greedy Algorithms): boss lo $= 10$ ; ab saare chaar reports block ho gaye. Total $= 10$ . Yeh step kyun? Greedy ka answer dikhane ke liye taaki hum use beat kar sakein.
DP — leaves pehle: har report $c$ ek leaf hai: $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$ . Yeh step kyun? Boss ko exclude karna saare chaar reports ko free kar deta hai; $4 \times 4 = 16$ .
Answer $= max (10, 16) = 16$ .

Verify: chaar reports invite karo (koi do adjacent nahi — woh sirf boss ke through connect hote hain), total $16 > 10$ . Greedy 6 se haarta hai. Yahi exactly reason hai ki Greedy Algorithms MWIS pe fail karte hain aur DP chahiye. ✓

Worked example

Ex 10 — Cell J: exam twist (negative weights) Same path $0 - 1 - 2$ lekin weights $w_{0} = 5, w_{1} = - 3, w_{2} = 5$ . Kya hume kabhi ek negative node include karna chahiye?

Forecast: node $1$ aapka score hurt karta hai. Kya DP phir bhi ise lene ka consider karta hai? Answer guess karo.

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$ . Yeh step kyun? Negative node include karna negative value deta hai — DP ise ek candidate ke roop mein rakhta hai lekin yeh haar jayega.
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$ . Yeh step kyun? $0$ ko include karna $1$ ko forbid karta hai, lekin hum phir bhi $f_{0} (1) = 5$ add karte hain (jisne khud node $2$ pakda tha). Yeh hume dono positive ends rakhne deta hai.
Answer $= max (10, 5) = 10$ , set ${0, 2}$ .

Verify: ${0, 2} = 5 + 5 = 10$ ; $- 3$ wala node include karna kabhi help nahi karta. Kyunki MWIS maximise karta hai, negative nodes silently drop ho jaate hain — lekin note karo: agar problem connectivity force karti toh tumhe ise include karna padta. Yahan skip karna free hai. ✓

Recall Quick self-test

Empty rod ki value ::: $r (0) = 0$ (empty set pe max $0$ define kiya gaya hai). 1-egg binary search kyun nahi use kar sakta? ::: Tuta hua egg chala jaata hai; aap back up nahi kar sakte, isliye linearly scan karna padta hai, cost $f$ . $F$ se $D$ ka bridge ::: $D (e, f) = min {d : F (e, d) \geq f}$ — fewest drops = pehla budget jiska reach $f$ cover kare. $F (2, d)$ recurrence ::: $F (2, d) = F (1, d - 1) + F (2, d - 1) + 1$ ; pehla $d$ jisme $F \geq f$ ho wahi answer hai. MWIS mein leaf node states ::: $f_{1} = w_{v}, f_{0} = 0$ (empty child-sum 0 hota hai). Greedy star tree pe kyun fail karta hai ::: Boss (10) chaar reports block karta hai; boss ko exclude karne se $4 \times 4 = 16 > 10$ milta hai.