Foundations — DP problems — rod cutting, egg drop, DP on trees

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

Is page par yeh assume kiya gaya hai ki aapne kuch bhi nahi dekha. Parent note padhne se pehle, aapko har woh symbol khud ka banana hoga jo woh aap par phenkta hai. Hum unhe ek ek karke banate hain, har ek earn karke, tabhi agla use karta hai.

0. Array kya hota hai, aur $p[i]$ ka kya matlab hai?

Ek array bas boxes ki ek row hoti hai, jisme har ek box ek number rakhta hai, aur har ek ko ek whole-number position se label kiya jaata hai jise index kehte hain.

• Picture: figure mein red box number $2$ hai; $p[2]$ woh number hai jo wahan rehta hai.
• Topic ko kyun chahiye: rod cutting ek price list $p[\mathrm{1..}n]$ store karta hai jahan $p[i]$ length $i$ ke rod-piece ki price hai. Indexing ke bina hum symbols mein "length-3 piece ki price" nahi keh sakte.

1. Notation $1\le i\le n$ aur "for all"

• Picture: $1$ se $n$ tak filled bar wali ek number line; andar har tick $i$ ki ek allowed value hai.
• Topic ko kyun chahiye: har DP recurrence bahut saare choices try karta hai — "pehla cut length $1$ ho sakta hai, ya $2$, ... $n$ tak". Range batati hai kaun se choices legal hain.

2. $\max$, $\min$, aur $\sum$ — teen loops-in-disguise

Yeh teen symbols har ek ka matlab hai "ek range ke through run karo aur values ko combine karo". Yeh parent ke har formula ka beating heart hain.

3. Functions aur notation $r(n)$, $D(e,f)$, $f(v,0)$

• Picture: ek box jisme arrows andar jaate hain (inputs) aur ek arrow bahar aata hai (jawab).
• Kyun ek input vs. do vs. do-with-a-flag:
  • $r(n)$ — rod revenue ek cheez par depend karta hai: rod ki length.
  • $D(e,f)$ — egg-drop cost do cheezon par depend karti hai: eggs bacha $e$ aur floors bacha $f$. Koi bhi badlo aur ek alag subproblem hai.
  • $f(v,0)$ / $f(v,1)$ — tree value node $v$ aur ek yes/no flag ($0$ = "$v$ excluded", $1$ = "$v$ included") par depend karti hai. Flag isliye hai kyunki parent ka decision jaanna chahta hai ki child ne kya decide kiya.

4. Recursion aur base cases — choti copies kahan se aati hain

• Picture: shrinking problems ki ek staircase; sabse neeche red step woh base case hai jo seedha answer return karta hai.
• Topic ko kyun chahiye: base case ke bina shrinking kabhi nahi rukta. Parent ka har recurrence ek general rule ko base cases ke saath pair karta hai — yeh required hai Recursion and Memoization se milne se pehle.

5. Overlapping subproblems aur memoization

• "Bottom-up" kyun: agar aap $r[0],r[1],r[2],\dots$ order mein fill karo, toh jab aap $r[j]$ compute karte ho har $r[j-i]$ jo use chahiye pehle se ho chuka hai. Koi recursion ki zaroorat nahi — bas ek ordered fill.

6. Big-O notation $O(n^2)$, $O(n)$ — cost tag

• Topic ko kyun chahiye: DP ka poora point speed hai. Rod cutting $O(n^2)$ hai (har $n$ lengths ke liye, $n$ tak first cuts try karo). Tree DP $O(n)$ hai (har edge ek baar touch hota hai). Is tag ke bina aap jeet appreciate nahi kar sakte.

7. Trees, nodes, children, aur DFS

• Picture: red node root hai; arrows neeche uske children ki taraf point karte hain; shaded blob ek subtree hai.
• Kyun no cycles matter karta hai: kyunki koi loops nahi hain, har subtree ek alag, independent subproblem hai — exactly woh condition jo DP ko chahiye. Yeh Tree Traversal (DFS) se connect hota hai.

Prerequisite map

Left side ki har cheez machinery build karti hai; sab parent note DP problems mein funnel hota hai. Yahan se aap Dynamic Programming, Recursion and Memoization, Knapsack Problem, aur Greedy Algorithms aur Binary Search ke saath contrasts ke liye ready ho.

Equipment checklist

Right side cover karo aur dekho kya aap ise zor se bol sakte ho.