DP problems — rod cutting, egg drop, DP on trees: Visual walkthrough

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

Step 1 — Rod kya hai, aur "revenue" kya hai?

KYA. Ek rod bas ek seedhi bar hai jisme whole-number length hoti hai. Length $n$ matlab woh $n$ units lambi hai. Hume ek price list $p$ di jaati hai: number $p [i]$ yeh batata hai ki length $i$ ka ek piece kitne coins mein bikta hai. Hume allow hai ki rod ko whole-number marks par kaatein aur har piece alag se bechein.

KYUN. Kisi bhi formula se pehle, hume us cheez par agree karna hoga jo hum count kar rahe hain. Yahan woh hai revenue — saare pieces se milne wale total coins. Pura game yeh hai: decide karo kahan kaatna hai taaki coins milkar maximum ho jaayein.

PICTURE. Neeche di gayi rod (length 4) aur uske neeche price ruler dekho. Har tick ek cuttable position hai. Amber numbers prices $p [1..4]$ hain.

Step 2 — Sabse important choice: sabse baayi taraf wala piece

KYA. Ek saath saare cuts imagine karne ki jagah (patterns exponentially zyada hain), hum sirf ek decision lete hain: left end se measure karte hue, pehla piece kitna lamba hai? Us length ko $i$ kaho. Phir us piece ko $p [i]$ mein becho aur usse hamesha ke liye bhool jao — jo bacha hai woh ek chhoti rod hai length $n - i$ ki.

KYUN. Yeh woh trick hai jo ek bade problem ko ek chote aur ek chhoti copy of itself mein tod deti hai. Rod kaatne ke har possible tarike mein koi na koi leftmost piece hoti hai. Toh agar hum $i$ ki har possible value consider karein, toh humne secretly har cutting pattern consider kar liya — bina unhe list kiye.

PICTURE. Red bracket length $i$ ke leftmost piece ko mark karta hai. Cyan bracket length $n - i$ ki leftover rod hai. Dhyan do leftover bas... ek aur rod hai. Same problem, chhoti.

Step 3 — Answer ko naam dena: function $r (n)$

KYA. $r (n)$ define karo = length $n$ ki rod se best revenue jo possibly mil sakti hai. Koi bhi revenue nahi — maximum.

KYUN. Hume "length $n$ ki rod ka answer" ke liye ek naam chahiye taaki jab leftover rod ( $n - i$ ) appear ho, toh hum uske best answer ko $r (n - i)$ keh sakein — wahi function, chhote input par call kiya gaya. Yahi problem ko khud par close karne deta hai.

PICTURE. $r (n)$ label wala box ek machine hai: isko ek length do, bahar best coins aate hain. Isko chhoti length do aur yeh khushi se phir se answer deta hai.

Step 4 — Recurrence ko term by term assemble karna

KYA. Ek fixed first-piece length $i$ ke liye, hamara total hai: pehle piece ke coins, $p [i]$ , plus leftover se best coins, $r (n - i)$ . Hume abhi best $i$ nahi pata, toh hum $1$ se $n$ tak har $i$ try karte hain aur sabse bada sum rakhte hain:

r (n) = 1 \leq i \leq n max (coins for the leftmost piece of length i p [i] + best coins from the leftover rod of length n - i r (n - i))

Is formula ke parts padhna:

$1 \leq i \leq n max$ ::: "har leftmost length $i$ try karo $1$ se $n$ tak, aur winner lo."
$p [i]$ ::: us pehle piece ke guaranteed coins — price list se ek known number.
$r (n - i)$ ::: us piece ke baad jo bhi hai uspar best kar sakate hain — same machine ek chhoti rod par.
$+$ ::: dono disjoint hain (piece aur leftover kabhi overlap nahi karte), toh unke coins simply add ho jaate hain.

$max$ KYUN. Yahan adversary hamari apni indecision hai — hum chahte hain sabse bada total, toh saare first-cut choices mein se woh choose karte hain jo sum maximize kare. Kyunki har cutting pattern kisi na kisi $i$ se capture hota hai, $i$ par max hi sachcha best hai.

PICTURE. Har row ek choice of $i$ hai; bar ki total length $p [i] + r (n - i)$ hai. Sabse tall (amber) bar woh winner hai jise $max$ select karta hai.

Step 5 — Naive recursion disaster kyun hai (aur fix kya hai)

KYA. Agar hum literally $r (n)$ ko ek function ki tarah code karein jo khud ko call kare, toh woh same chhoti rods baar baar recompute karta hai. $r (4)$ ko $r (3), r (2), r (1)$ chahiye; lekin $r (3)$ ko bhi $r (2), r (1)$ chahiye; aur $r (2)$ ko $r (1)$ phir chahiye. Same node call tree mein blast ho jaata hai.

KYUN yeh fatal hai. Repeated calls ki count exponentially badhti hai ( $\sim 2^{n}$ ). Phir bhi genuinely alag sawaal sirf $n + 1$ hain: $r (0), r (1), \dots, r (n)$ . Hum muthi bhar sawaalon ko billions of times re-answer kar rahe hain.

FIX. Har answer ko pehli baar compute karte waqt store kar lo. Yeh hai memoization (top-down) ya ek filled table (bottom-up). Ab har $r (j)$ sirf ek baar compute hoga.

PICTURE. Left: exploding recursion tree, duplicate nodes red glow kar rahe hain. Right: wahi kaam ek single row of $n + 1$ boxes mein collapse ho gaya, har ek sirf ek baar fill hota hai.

Step 6 — Table ko bottom-up fill karna

KYA. Neeche recurse karne ki jagah, hum $r$ ko upar build karte hain: $r [1]$ compute karo, phir $r [2]$ , ... har ek array mein pehle se baithe answers use karta hai. Cuts reconstruct karne ke liye, hum $cut [j]$ mein bhi store karte hain winning leftmost length $i$ .

r [j] = 1 \leq i \leq j max (p [i] + r [j - i])

$r [j]$ ::: woh box jo hum abhi fill kar rahe hain (length $j$ ke liye best revenue).
$r [j - i]$ ::: ek box jo pehle hi fill ho chuka hai (ek chhoti rod), toh yeh bas ek lookup hai — koi recursion nahi.
$cut [j]$ ::: yaad rakhta hai kaun sa $i$ jeeta, taaki hum baad mein actual pieces rebuild kar sakein.

KYUN left-to-right kaam karta hai. Jab hum box $j$ fill karte hain, har woh box jo ise chahiye ( $0$ se $j - 1$ tak) pehle se ho chuka hai. Koi box apne right wale box ka wait nahi karta.

PICTURE. $p = [_, 1, 5, 8, 9]$ , $n = 4$ ke liye table. Arrows dikhate hain ki box $j = 4$ earlier boxes $r [3], r [2], r [1], r [0]$ se pull kar raha hai jaise $i$ $1, 2, 3, 4$ par range karta hai.

Step 7 — Har edge case, taaki kuch bhi surprise na kare

KYA. Hum boundary aur degenerate inputs check karte hain taaki reader kabhi kisi unshown scenario mein na phase:

$n = 0$ (empty rod). $r (0) = 0$ base case se. $max$ loop kabhi nahi chalta (koi valid $i$ nahi). ✔
$n = 1$ (sabse chhoti real rod). Sirf $i = 1$ allow hai: $r (1) = p [1] + r (0) = p [1]$ . ✔
"Bilkul mat kaato" included hai. $i = n$ choose karna $p [n] + r (0) = p [n]$ deta hai — pure rod ko bina kaate bechna. Yeh bas unhi candidates mein se ek hai jo $max$ compare karta hai, toh koi special case zaroorat nahi. ✔
Ek price jo "bahut sasti" hai. Agar $p [i]$ chhota hai, toh term $p [i] + r [j - i]$ bas $max$ haar jaata hai; kuch nahi tutata. $p [i] = 0$ bhi theek hai.

KYUN yeh dikhate hain. DP correctness boundary par hi jeeti ya haari jaati hai. Agar $r (0)$ galat hota, toh har baad wala box jo usar build hua woh poisoned hota. "Whole becho" case ka automatic hona hi prove karta hai ki hume kabhi "zero cuts" ke liye extra branch ki zaroorat nahi.

PICTURE. Teen mini-rods: length 0 (kuch nahi, value 0), length 1 (ek option), aur uncut length- $n$ rod jo single-piece candidate ke roop mein same $max$ mein feed ho rahi hai.

Recall Edges par khud ko check karo

$r (0)$ kya hai aur kyun? ::: $0$ — ek empty rod mein bechne ke liye koi piece nahi; yeh woh base case hai jis par baaki har value build hoti hai. Recurrence "koi cut mat karo" ko kaise handle karta hai? ::: $i = n$ ke zariye, $p [n] + r (0) = p [n]$ deta hai; yeh $max$ ke andar ek candidate hai, toh koi special branch zaroorat nahi. Table ko chhote $j$ se bade $j$ ki taraf kyun fill karna chahiye? ::: Kyunki $r [j]$ chhote indices ke liye $r [j - i]$ read karta hai — woh pehle se computed hone chahiye.

Ek-picture summary

Is page par sab kuch ek figure mein compress kiya gaya: leftmost-piece choice (Step 2) recurrence ban jaata hai (Step 4), recurrence ek table ko left-to-right fill karta hai (Step 6), aur reconstruction $cut$ pointers ko actual pieces mein wapas walk karta hai.

Recall Feynman retelling — plain words mein kaho

Socho tum ek bar bech rahe ho aur koi tumhe length ke hisaab se price list deta hai. Tum ise ek paaglon ki tarah kaatne ke har crazy tarike try nahi karte — yeh toh nightmare hai. Iske badle tum ek chota sa sawaal poochte ho: pehla piece jo main todta hoon woh kitna lamba hai? Tum har possible first length try karte ho, uski price pocket mein rakhte ho, phir baaki ki bar khud ko wapas dete ho aur exactly wahi sawaal poochte ho — lekin ab bar chhoti hai, toh yeh usi puzzle ka ek aasaan version hai. "Length $L$ ki bar ke liye best coins" ke jawab ko $r (L)$ kehte hain, aur yeh equal hai: har first-length $i$ ke liye, price $p [i]$ ko leftover par best $r (L - i)$ mein add karo, aur sabse bada rakho. Base case hai $r (0) = 0$ : ek empty bar ki koi value nahi. Sirf ek clever baat hai: usi chhoti bar ko do baar mat solve karo — pehli baar answer ek chhote box mein likh lo, phir bas box padho. Bas yahi poora idea hai: recursion with a notepad, length $1$ se upar boxes fill karo, aur end mein actual pieces rebuild karne ke liye breadcrumbs (kaun sa first-cut jeeta) follow karo.

Recall Connections

Yeh walkthrough Dynamic Programming paradigm ka visual companion hai aur directly Recursion and Memoization par lean karta hai. Iske "try-every-first-choice" flavour ko Greedy Algorithms (jo ek choice par commit karta hai) se compare karo, Binary Search se (egg-drop cousin ko speed karne ke liye use hota hai), Tree Traversal (DFS) se (DP-on-trees ka engine), aur Knapsack Problem se (rod cutting ka closest structural sibling). Full context: parent topic note.

$j$	har $i$ try karo ( $p [i] + r [j - i]$ )	$r [j]$	winning $i$
1	$1 + 0 = 1$	1	1
2	$max (1 + 1, 5 + 0) = max (2, 5)$	5	2
3	$max (1 + 5, 5 + 1, 8 + 0) = max (6, 6, 8)$	8	3
4	$max (1 + 8, 5 + 5, 8 + 1, 9 + 0) = max (9, 10, 9, 9)$	10	2