Foundations — Tabulation (bottom-up DP) — iterative

3.7.8 · D1 · Coding › Algorithm Paradigms › Tabulation (bottom-up DP) — iterative

Is page pe assume kiya gaya hai ki tumne kuch bhi nahi dekha. Pehle tumhe parent note Tabulation (bottom-up DP) padhne se pehle ye jaanna zaroori hai ki array, index, subproblem, recurrence, base case, aur max, substructure, aur overlapping words ka matlab kya hai — pictures ki tarah, jargon ki tarah nahi. Hum har ek ko order mein banate hain, har ek pichle wale ka use karke.

0. "Problem" aur "subproblem" kya hota hai?

Picture: ek bada box socho jis par likha ho "climb 5". Uske andar chote identical boxes chhuppe hain: "climb 4", "climb 3", … "climb 0" tak. Har box apne aap answerable hai, aur bade box ka answer chote boxes ke answers se bana hota hai.

Topic ko iske baare mein kyun chahiye: tabulation literally "pehle saare chote boxes answer karo, phir combine karo" hai. Agar ye idea hi nahi ki ek problem apne andar khud ke chote versions rakhta hai, toh store karne ke liye kuch nahi hai aur build up karne ke liye bhi kuch nahi.

1. Array — numbered boxes ki ek row

Picture: socho ek egg carton flat rakha ho. Six cups ek line mein. Har cup ek number rakh sakta hai.

Topic ko iske baare mein kyun chahiye: tabulation mein "table" EK array hi hai. Ye woh jagah hai jahan hum har chota answer likhte hain taaki hume use dubara compute na karna pade. Table word aur array word yahan ek hi physical cheez ko refer karte hain.

2. Index $i$ — box ka house number

Picture: egg-carton ke cups $0,1,2,3,4,5$ left se right numbered hain — 1 se nahi shuru hote. Bilkul pehla cup house number $0$ hai. Ye ek convention hai jo almost saara code use karta hai; ise ab apni haddiyon mein daal lo.

Topic ko iske baare mein kyun chahiye: parent note ki har recurrence indices use karke likhi hai — $dp[i]$, $dp[i-1]$, $dp[i-2]$. Agar $i-1$ aur $i-2$ confuse karte hain, toh koi bhi recurrence samajh nahi aayegi.

3. Neighbours: $dp[i-1]$ aur $dp[i-2]$

Ab jab $i$ ek house number hai, notation $dp[i-1]$ bas ek step left wala box hai, aur $dp[i-2]$ do steps left wala hai.

Picture: cup $4$ par khade ho. Left mein cup $3$ aur cup $2$ tak pahuncho. Dono mein already numbers hain, toh tum unhe add karke result cup $4$ mein daal sakte ho. Tum kabhi right (unfilled cups ki taraf) nahi pahunchte.

4. Base case — woh boxes jo tum haath se bharte ho

Picture: cup $1$ se "do steps left" tak nahi pahunch sakte — woh cup $-1$ hoga, jo exist nahi karta. Toh cups $0$ aur $1$ haath se rakhne zaroori hain pehle loop shuru ho. Ye woh zameen hai jis par tum khade ho.

Topic ko iske baare mein kyun chahiye: recurrence $dp[i]=dp[i-1]+dp[i-2]$ bilkul shuruat mein undefined hai (woh array ke edge se bahar padhega). Base cases woh hole band karte hain. Inhe bhool jaao aur poora table zero rahega ya program $dp[-1]$ padhte waqt crash kar jaayega.

5. Recurrence — woh rule jo ek box ko uske neighbours se jodata hai

Ise English mein padho: "position $i$ par answer, $i-1$ par answer aur $i-2$ par answer ke barabar hai." Equals sign yahan aise compute hota hai maanta hai.

Topic ko iske baare mein kyun chahiye: recurrence loop ka engine hai. Base cases pehle do rungs dete hain; recurrence uske baad har rung banata hai. Aise relations kyun valid hote hain iska deeper math Recurrence Relations mein hai.

6. Symbols $+$ vs $\max$ — aur topic dono ke beech switch kyun karta hai

Parent note mein do alag DP problems do alag combining operations use karti hain. Tumhe jaanna zaroori hai ki kab kaun sa sahi hai.

• $+$ (addition) use karo jab tum cheezein count kar rahe ho. Climbing Stairs mein, aakhri move ya 1-step ya 2-step tha. Paths ke ye do groups overlap nahi karte, toh total count group A plus group B hai. Disjoint possibilities count karna ⇒ add.
• $\max$ use karo jab tum optimise kar rahe ho (best chahiye). 0/1 Knapsack mein tum ya toh koi item lete ho ya skip karte ho, aur jo zyada value deta hai woh chahiye. Tum count nahi kar rahe — tum winner choose kar rahe ho ⇒ max.

7. 2D table — $dp[i][c]$, do house numbers wale boxes

Kuch problems ko ek waqt mein do parameters chahiye hoti hain. Tab table ek grid ban jaata hai aur har box ke do indices hote hain: ek row $i$ aur ek column $c$.

Picture: cups ka ek chessboard. Ek cup fill karne ke liye, tum ab upar wali row ($i-1$) ke cups aur kuch columns left ($c-w$) dekhte ho. Jab tak poori pichli row finish ho, current row kisi bhi order mein fill ho sakti hai.

Topic ko iske baare mein kyun chahiye: 0-1 Knapsack aur Longest Common Subsequence dono ek saath do cheezein track karte hain (kaun se items / kaun se characters, aur remaining capacity / position), toh ek 1D row kaafi nahi hai.

8. Optimal substructure aur overlapping subproblems — do admission tickets

Ye woh do properties hain jo ek problem mein HONI CHAHIYE tabulation allowed hone se pehle.

Picture: calls ka ek family tree jahan same node (jaise "climb 2") kai branches mein appear karta hai. Overlapping = tree mein repeated nodes hain. Substructure = har parent node ki value uske children ki values ka clean combination hai.

Topic ko iske baare mein kyun chahiye: ye dono milke define karte hain Dynamic Programming (Dynamic Programming). Tabulation aur uska cousin Memoization (top-down DP) bas inhe exploit karne ki do directions hain — bottom-up vs top-down.

Prerequisite map

Har arrow "samajhne ke liye zaroori hai" padha jaata hai. Koi bhi path top se bottom tak follow karo aur tum, poori tayyari ke saath, Tabulation par pahunch jaate ho.

Equipment checklist

Right side cover karo aur khud test karo. Agar koi bhi answer fuzzy lage, parent note kholne se pehle upar woh section dobara padho.

Connections

• Tabulation (bottom-up DP) — iterative — woh parent topic jise ye foundations unlock karte hain
• Dynamic Programming — woh paradigm jo do admission tickets se define hota hai
• Optimal Substructure aur Overlapping Subproblems — dono properties, depth mein
• Recurrence Relations — step 5 ke peeche ka math
• Memoization (top-down DP) — tabulation ka top-down twin
• 0-1 Knapsack, Longest Common Subsequence, Coin Change — jahan 2D tables appear hoti hain
• Space Optimization in DP — table ko shrink karna jab tum ise samajh lo