DP problems — rod cutting, egg drop, DP on trees: Question bank

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

Definition Is page par use kiye gaye symbols aur recurrences

Traps tackle karne se pehle, yahan har symbol aur formula plain words mein ek jagah diya gaya hai.

Rod cutting. Ek rod ki integer length $n$ hai. ==Price array $p [1.. n]$ == mein $p [i]$ = length $i$ ka ek piece bechne par milne wala paisa (index 0 unused hai, aur hum $p [0] = 0$ set karte hain). Define karo == $r (n)$ == = length $n$ ki rod se milne wali best total revenue. Iska recurrence, har possible leftmost piece length $i$ ko try karte hue: $r (n) = max_{1 \leq i \leq n} (p [i] + r (n - i)), r (0) = 0.$ Bottom-up array version mein $r [j]$ ko $r (j)$ likhte hain, toh $r [j - i]$ ka matlab hai "length $j - i$ ki baaki rod ki best revenue".

Egg drop. == $e$ eggs aur $f$ floors ke saath, define karo $D (e, f)$ == = worst case mein threshold floor dhundhne ki guaranteed minimum drops ki sankhya. Tum floor $x$ se drop karte ho; ya toh tutta hai (threshold $x$ par ya neeche, $x - 1$ floors bache, ek egg kam) ya bach jaata hai ( $x$ ke upar $f - x$ floors, same eggs): $D (e, f) = 1 + min_{1 \leq x \leq f} max (D (e - 1, x - 1), D (e, f - x)) .$ Base cases: $D (e, 0) = 0$ , $D (e, 1) = 1$ , $D (1, f) = f$ . Dual quantity == $F (e, d)$ == = $e$ eggs aur $d$ drops se maximum floors jo fully resolve ho sakti hain: $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1, F (e, 0) = F (0, d) = 0.$

DP on trees — MWIS. ==MWIS = Maximum Weighted Independent Set==: har node $v$ ka ek ==weight $w_{v}$ == hai, aur hum aise nodes ka set choose karte hain jahan koi bhi do adjacent na hon aur total weight sabse zyada ho. $c$ ko ==children of $v$ == par range karne do (likha $c \in ch (v)$ ). Do states: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} f (c, 0), f (v, 0) = \sum_{c \in ch (v)} max (f (c, 1), f (c, 0)) .$ Yahan $f (v, 1)$ = $v$ included hone par best subtree weight, $f (v, 0)$ = $v$ excluded hone par best; answer hai $max (f (root, 1), f (root, 0))$ .

True or false — justify karo

Recall Reveal all

Rod cutting mein cuts integer positions par hi honi chahiye. ::: True — price array $p [1.. n]$ sirf integer lengths ke liye values define karta hai, toh "length 2.5 ka piece" ki koi defined price nahi hai; poora model integers par hi hai. Rod cutting mein leftmost piece ko $1.. n$ par loop karna kuch cuttings miss karta hai kyunki yeh rightmost piece kabhi fix nahi karta. ::: False — har cutting ka exactly ek leftmost piece hota hai, toh saari leftmost lengths par iterate karna aur baaki par recurse karna har arrangement cover kar leta hai; rightmost fix karna wohi baat kahne ka ek redundant doosra tarika hoga. Egg drop ka answer $D (e, f)$ kabhi $f$ se zyada nahi ho sakta. ::: True — ek-egg strategy (floor by floor scan) hamesha kaam karti hai aur zyada se zyada $f$ drops lagti hai, toh zyada eggs sirf help kar sakte hain; $D (e, f) \leq D (1, f) = f$ . Unlimited eggs ke saath, egg drop binary search mein collapse ho jaata hai aur answer $⌈ lo g_{2} (f + 1)⌉$ hota hai. ::: True — jab eggs wafir hon toh break kabhi catastrophic nahi, isliye har drop baaki candidate floors plus "no floor" outcome ko half mein split kar sakta hai; $k$ drops mein at most $2^{k}$ outcomes distinguish hote hain, aur $f + 1$ possible thresholds hain (floors $1.. f$ ya "kabhi nahi tutta"), toh $2^{k} \geq f + 1$ chahiye, yaani $k = ⌈ lo g_{2} (f + 1)⌉$ . DP on trees mein do states $f (v, 0)$ aur $f (v, 1)$ isliye chahiye kyunki ek node ka optimal contribution ek aisi choice par depend karta hai jo uske parent ne abhi tak nahi ki. ::: True — parent ko jaanna hai "agar main tumhe loon toh tumhara best kya hai" versus "agar na loon toh", toh child dono publish karta hai aur parent choose karta hai. Tree par MWIS ko greedily solve kiya ja sakta hai hamesha pehle leaves pick karke. ::: False in general — leaves pick karna ek heuristic hai jo haar sakta hai; har subtree ke liye include-vs-exclude compare karne waala do-state DP hi optimality guarantee karta hai. Rod-cutting recurrence essentially unbounded knapsack ka disguise hai. ::: True — har length $i$ ek "weight" $i$ aur value $p [i]$ waala reusable item hai, capacity $n$ ; dekho Knapsack Problem. Top-down rod-cutting recursion ko memoize karna jo answer return hota hai use change karta hai. ::: False — memoization sirf recomputation hatata hai; value plain recursion jitni hi identical hai, bas $O (n^{2})$ mein chalta hai exponential time ki jagah.

Error dhundho

Recall Reveal all

"Rod cutting base case: $r (1) = 0$ kyunki length-1 rod cut nahi ho sakti." ::: Error — cut karna zaroori nahi hai. $r (1) = p [1]$ : "zero cuts" option (poora piece bechna) hamesha allowed hai, toh $r (1)$ length 1 ki price ke barabar hai, 0 nahi. "Egg drop: jab floor $x$ par egg breaks karta hai, toh sub-problem neeche $D (e - 1, x)$ floors ka hai." ::: Error — break ka matlab hai threshold $x$ par ya neeche hai, bacha $x - 1$ floors test karne ke liye (floor $x$ khud ab ek breaking floor jaana gaya), toh yeh $D (e - 1, x - 1)$ hai. "Egg drop: break case aur survive case ka min lo, kyunki hum better outcome ki umeed rakhte hain." ::: Error — tum control nahi kar sakte kya hoga; adversary (worst case) decide karta hai, toh tumhe dono ka max lena hoga, phir $x$ par minimize karo. "MWIS: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} max (f (c, 0), f (c, 1))$ ." ::: Error — agar $v$ included hai, toh koi bhi child included nahi ho sakta, toh har child state 0 par forced hai: $f (v, 1) = w_{v} + \sum_{c \in ch (v)} f (c, 0)$ . $max$ sirf $f (v, 0)$ mein aata hai. "MWIS: answer $f (root, 1)$ hai kyunki root ko include karna sabse zyada weight pakadta hai." ::: Error — root ko bahar rakhna better ho sakta hai; answer hai $max (f (root, 1), f (root, 0))$ . "Tree par DP mein nodes ko root-first (pre-order) process karna padta hai taaki root ka answer ready ho." ::: Error — ek node ko pehle apne children ke answers chahiye, toh tum leaves-up (post-order / DFS return) process karte ho; root last compute hota hai, pehle nahi. "Rod cutting $O (n)$ hai kyunki tum size $n$ ka ek array bharte ho." ::: Error — entry $r [j]$ fill karne mein $j$ trials tak ka inner loop lagta hai, toh total $O (n^{2})$ hai, $O (n)$ nahi.

Why questions

Recall Reveal all

DP in teeno problems ke liye specifically brute force se kyun jeetata hai? ::: Kyunki wohi subproblem (chhoti rod / kam eggs-floors / same subtree) naive tree mein exponentially baar repeat hota hai; har ek ko ek baar solve karke cache karna exponential ko polynomial mein badal deta hai. Tree case $O (n)$ kyun hai jabki rod cutting $O (n^{2})$ hai? ::: Tree mein har edge exactly ek baar touch hoti hai (har child apne parent ko ek baar feed karta hai), jabki rod cutting har $j$ par saari chhoti lengths re-scan karti hai, ek quadratic double loop deta hai. Egg drop $x$ par $min$ kyun use karta hai lekin outcomes par $max$ kyun? ::: Tum apne fayde ke liye drop floor $x$ choose karte ho (min), lekin tum choose nahi kar sakte ki yeh tutega ya nahi — nature/adversary bura branch choose karta hai (max). Hum yahan rod-cutting item-once logic reuse kyun nahi kar sakte — yeh unbounded kyun hai? ::: Length- $i$ ka piece baar baar cut out ho sakta hai (length-6 rod teen length-2 pieces ho sakti hai), toh har "item" reusable hai, 0/1 knapsack ki tarah nahi; isliye recurrence $r [j - i]$ par recurse karta hai (wahi rod phir se), item $i$ hatake nahi. "Dual" egg-drop view $F (e, d) = F (e - 1, d - 1) + F (e, d - 1) + 1$ zyada fast kyun kaam karta hai? ::: Yeh question flip karta hai " $d$ drops aur $e$ eggs se main kitne floors clear kar sakta hun?"; drop break-branch ( $F (e - 1, d - 1)$ ), survive-branch ( $F (e, d - 1)$ ), aur current floor mein floors split karta hai. Dual $F (e, d)$ se $D (e, f)$ recover kaise karte hain? ::: Kyunki $F$ strictly $d$ mein increasing hai, " $\geq f$ floors clear karne wale fewest drops" matlab hai "pehla $d$ jahan $F (e, d) \geq f$ "; $d = 1, 2, 3, \dots$ scan karo aur pehle wale par ruko jo $f$ tak pahunche — woh $d$ hi $D (e, f)$ hai, kyunki $F (e, D (e, f)) \geq f$ lekin $F (e, D (e, f) - 1) < f$ . MWIS mein subtrees cleanly add kyun hote hain lekin ek parent–child edge par "sirf add karna" fail kyun karta hai? ::: Sibling subtrees disjoint hain (shared nodes nahi, unke beech adjacency nahi) toh unke optima add hote hain; parent aur child adjacent hain, toh dono ek saath pick nahi ho sakte — yahi single constraint hai jo do states handle karti hain. Greedy kuch problems ke liye sahi kyun hai lekin MWIS ke liye nahi? ::: Greedy Algorithms tabhi kaam karte hain jab local best globally optimal guaranteed ho (matroid-like structure); MWIS mein yeh nahi hai kyunki ek heavy node neighbors ko block karta hai jinका combined weight use exceed kar sakta hai.

Edge cases

Recall Reveal all

$n = 0$ ke saath rod cutting: $r (0)$ kya hai? ::: $r (0) = 0$ — ek empty rod koi revenue nahi deti; yeh base case har lambi recurrence ko anchor karta hai. Rod cutting jahan poora bechna hamesha jeetata hai — kya algorithm phir bhi cut karta hai? ::: Nahi — leftmost piece $i = n$ try karne par $r (0) = 0$ bachta hai, $p [n]$ deta hai; agar woh max hai, toh cut[n]=n ek single (trivial) piece record karta hai, yaani koi real cut nahi. Single egg ke saath egg drop, $e = 1$ , arbitrary $f$ : $D (1, f)$ kya hai? ::: $D (1, f) = f$ — ek egg bottom-up linear scan force karta hai (break permanent hai, toh tum koi floor skip nahi kar sakte), worst case mein $f$ drops lagte hain. $e = 0$ eggs aur $f \geq 1$ floors ke saath egg drop: $D (0, f)$ kya hona chahiye? ::: Undefined / impossible ( $\infty$ ) — koi eggs nahi toh tum koi floor test nahi kar sakte, toh koi finite strategy $T$ dhundhne ki guarantee nahi deti; sirf $D (e, 0) = 0$ safe zero hai. $f = 0$ floors ke saath egg drop: har $e$ ke liye $D (e, 0) = 0$ kyun hai? ::: Kuch identify karna baaki nahi — zero floors matlab threshold question already resolved hai, toh egg count chahe kuch bhi ho, zero drops chahiye. Egg drop, exactly 1 floor: $D (e, 1) = 1$ kyun hai aur 0 kyun nahi? ::: Tumhe abhi bhi confirm karna hai ki kya woh single floor ek breaking floor hai, jiske liye ek drop chahiye; building ka exist karna threshold jaanna nahi hai. Empty tree (zero nodes) par MWIS: answer kya hai? ::: $0$ — empty set $\emptyset$ ek valid independent set hai jiska total weight 0 hai; DFS kabhi nahi chalta, koi state set nahi hoti aur base return 0 hai. Single-node tree par MWIS: answer kya hai? ::: $max (f (v, 0), f (v, 1)) = max (0, w_{v}) = w_{v}$ agar $w_{v} > 0$ ; ek akela node ka koi neighbor nahi jo use block kare. Saare-negative weights ke saath MWIS: kya DP phir bhi kaam karta hai? ::: Haan — exclude state $f (v, 0)$ har node ko bahar rakh sakta hai (0 contribute karte hue), toh answer $\geq 0$ hai; "empty set" hamesha ek legal independent set hai. Ek path graph (ek degenerate "tree" jo ek line hai): kya tree-MWIS abhi bhi apply hoti hai? ::: Haan — ise ek end par root karo aur DFS karo; recurrence classic 1-D house-robber DP mein reduce ho jaati hai, kyunki har node ka at most ek child hota hai. Star graph, centre weight 10, chaar leaves weight 4: DP kya output karta hai aur greedy kyun fail karta hai? ::: DP $16$ output karta hai (saari chaar leaves), kyunki centre exclude karne par har leaf free ho jaati hai; greedy pehle centre (10) pakad leta hai, saari leaves block kar deta hai, aur haar jaata hai — do-state comparison yeh globally pakad leta hai.