Tabulation (bottom-up DP) — iterative: Visual walkthrough

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

Hum poore time parent ka wahi example use karte hain:

Neeche ki sab cheez ek idea par bani hai Optimal Substructure se: pure bag ka best answer chhote bags ke best answers se banta hai, fewer items ke saath. Hume bas woh chhote answers pehle likhne hote hain — yahi tabulation hai.

Step 1 — Table draw karo aur box ka matlab batao

KYA. Hum ek grid banate hain. Rows = "hum kitne items use karne ki permission rakhte hain", columns = "bag abhi kitna bada hai".

KYUN. Koi bhi number likhne se pehle, ek DP ko answer dena hota hai "ek box ka matlab kya hai?" Agar ek box ka koi clear English meaning nahi hai, toh har agla step guesswork hai. Hum define karte hain:

$d p [i] [c] = best total value using only the first i items i items, if the bag holds at most capacity c weight.$

$i$ range karta hai $0, 1, 2, 3$ — $i = 0$ matlab "tumhe koi item allowed nahi".
$c$ range karta hai $0, 1, 2, 3, 4$ — $c$ ek pretend chhoti capacity hai, hamesha real $4$ nahi. Hume yeh chhote bags chahiye kyunki item lene se remaining room kam ho jaata hai.

PICTURE. Khali grid. Labels dekho: har cell ek question hai ("itne items aur itne room ke saath best value kya hai?") jo answer ka wait kar rahi hai.

Figure — Tabulation (bottom-up DP) — iterative

Step 2 — Base row fill karo (zero items = zero value)

KYA. Puri top row $i = 0$ ko $0$ se fill karo.

KYUN. Jab koi item allowed nahi, bag mein daalne ke liye kuch nahi hai, chahe bag kitna bhi bada ho. Toh best value har capacity ke liye $0$ hai:

$d p [0] [c] = 0 for all c .$

$d p [0] [c]$ — woh row jahan zero items permitted hain.
$= 0$ — khali bag, khali value.

Yeh recurrence ka seed hai. Iske bina, har baad wala cell jo "peeche dekhta" hai ek khali box read karega aur pura build collapse ho jaayega. Yeh exactly parent ki warning hai: base case bhool jaao aur sab 0 rahega ya crash karega — siwaaye yahan 0 sahi hai, isliye hum ise purposely set karte hain.

PICTURE. Zeros ki green base row. Derivation mein har arrow eventually is row tak trace hoti hai.

Step 3 — Woh choice jo har doosra cell banati hai: lo ya skip karo

KYA. Kisi bhi cell $d p [i] [c]$ ke liye hum imagine karte hain ki hum item $i$ ke saamne khade hain, $c$ hold karne waale bag ke saath. Hamare paas exactly do moves hain.

KYUN. Har item ya to bag mein hai ya bahar. Yeh do possibilities sab kuch cover karti hain aur kabhi overlap nahi karti — toh best answer donon mein se better hai:

$d p [i] [c] = max (skip item i d p [i - 1] [c], take item i v_{i} + d p [i - 1] [c - w_{i}])$

Har piece slowly padho:

$d p [i - 1] [c]$ — skip: pretend karo item $i$ exist hi nahi karta. Same bag $c$ , lekin ab sirf pehle $i - 1$ items. Room $c$ untouched rehta hai.
$v_{i}$ — woh reward jo hum item $i$ lekar grab karte hain.
$c - w_{i}$ — item $i$ apna weight $w_{i}$ khaane ke baad bacha hua room.
$d p [i - 1] [c - w_{i}]$ — us baache hue room mein pehle items ke saath best jo hum abhi bhi kar sakte hain.
$max (\dots)$ — hum pehle se nahi jaante kaunsa move better hai, toh dono compute karte hain aur winner rakhte hain.

PICTURE. Do branches ek cell se arrows ki tarah nikli hain: skip arrow seedha upar jaata hai, take arrow $w_{i}$ columns upar-aur-left jaata hai aur $v_{i}$ add karta hai.

Step 4 — Guard: agar item zyada heavy ho toh?

KYA. $max$ se pehle, hume check karna hoga: kya item $i$ fit bhi hota hai?

KYUN. "Take" branch $d p [i - 1] [c - w_{i}]$ read karta hai. Agar $w_{i} > c$ , toh $c - w_{i}$ negative hai — negative room wala bag, jo bakwaas hai (aur code mein out-of-bounds index). Toh jab item zyada heavy ho, lena ek option nahi hai aur sirf skipping bachta hai:

$d p [i] [c] = {d p [i - 1] [c] max (d p [i - 1] [c], v_{i} + d p [i - 1] [c - w_{i}]) if w_{i} > c (doesn’t fit) if w_{i} \leq c (fits)$

Top line degenerate case hai — koi choice nahi, bas upar se value carry karo.
Bottom line Step 3 wali full two-way choice hai.

Yeh ek case hai jo hume explicitly cover karna hai, warna reader ek negative index hit karta hai jo kabhi handle hota hua nahi dikhta.

PICTURE. Side by side do mini-cells: ek jahan item bag se zyada heavy hai (sirf up arrow legal hai, take arrow red mein cross out hai), ek jahan fit hota hai (dono arrows legal).

Step 5 — Row 1 fill karo (sirf item 1 available, weight 1, value 1)

KYA. $d p [1] [c]$ compute karo $c = 0, 1, 2, 3, 4$ ke liye, sirf upar ki zero-row se padho.

KYUN. Item 1 ka weight $w_{1} = 1$ , value $v_{1} = 1$ hai.

$c = 0$ : bag kuch hold nahi karta, item weight $1 > 0$ → fit nahi hota → $d p [1] [0] = d p [0] [0] = 0$ .
$c = 1$ : fit hota hai. $max (d p [0] [1], 1 + d p [0] [1 - 1]) = max (0, 1 + 0) = 1$ .
$c = 2, 3, 4$ : item abhi bhi fit hota hai, aur leftover room kuch naya nahi add karta (sirf ek item exist karta hai), toh har ek $max (0, 1 + 0) = 1$ hai.

Row 1: $[0, 1, 1, 1, 1]$ .

PICTURE. Row 1 filled, $d p [1] [1]$ ka arrow dikhaya gaya hai: skip-branch upar ka $0$ read karta hai, take-branch ek column upar-left jaata hai, $0$ read karta hai, $v_{1} = 1$ add karta hai, jeet jaata hai.

Step 6 — Row 2 fill karo (item 2 ab allowed, weight 3, value 4)

KYA. $d p [2] [c]$ compute karo, sirf row 1 se padho (Step 5 mein already done).

KYUN. Item 2 ka $w_{2} = 3$ , $v_{2} = 4$ hai.

$c = 0, 1, 2$ : $w_{2} = 3 > c$ → fit nahi hota → upar se copy karo: $d p [2] [c] = d p [1] [c] = 0, 1, 1$ .
$c = 3$ : fit hota hai. $max (d p [1] [3], 4 + d p [1] [3 - 3]) = max (1, 4 + d p [1] [0]) = max (1, 4 + 0) = 4$ .
$c = 4$ : fit hota hai. $max (d p [1] [4], 4 + d p [1] [4 - 3]) = max (1, 4 + d p [1] [1]) = max (1, 4 + 1) = 5$ .

Row 2: $[0, 1, 1, 4, 5]$ .

Notice karo $d p [2] [4] = 5$ : yeh item 1 aur item 2 dono saath hain (value $1 + 4$ ), aur recurrence ne ise automatically $v_{2}$ ko leftover-room answer $d p [1] [1] = 1$ mein add karke find kiya.

PICTURE. Row 2 filled. Star cell $d p [2] [4]$ apna take-arrow $w_{2} = 3$ columns upar-left $d p [1] [1]$ mein jaata hua dikhata hai, plus $+ 4$ .

Step 7 — Row 3 fill karo aur answer padho (item 3, weight 4, value 5)

KYA. Last row $d p [3] [c]$ compute karo, sirf row 2 se padho. Final answer $d p [3] [4]$ par rehta hai.

KYUN. Item 3 ka $w_{3} = 4$ , $v_{3} = 5$ hai.

$c = 0, 1, 2, 3$ : $w_{3} = 4 > c$ → fit nahi hota → row 2 copy karo: $0, 1, 1, 4$ .
$c = 4$ : fit hota hai. $max (d p [2] [4], 5 + d p [2] [4 - 4]) = max (5, 5 + d p [2] [0]) = max (5, 5 + 0) = 5$ .

Row 3: $[0, 1, 1, 4, 5]$ .

Answer hai $d p [3] [4] = 5$ . Yahan ek subtle, beautiful baat hai: yeh ek tie hai. Item 3 akele $5$ deta hai; previous row already $5$ had (items 1+2). $max$ either way $5$ rakhta hai — dono plans optimal hain. Yahi woh tie hai jiska parent ne hint diya tha, ab derived, assert nahi kiya.

PICTURE. Pura table, bottom-right corner amber glow kar raha hai answer ke taur par, dono winning routes (item 3 akela; items 1+2) trace kiye gaye hain.

Step 8 — Fill order kyun kabhi backwards nahi ja sakta

KYA. Humne hamesha row by row, top to bottom fill kiya ( $i$ small → large).

KYUN. Har cell $d p [i] [c]$ sirf row $i - 1$ se padta hai. Toh jab hum row $i$ start karte hain, row $i - 1$ already 100% complete hai. Yahi wajah hai ki tabulation loops small → large chalaate hain, exactly reverse us tarike ke jo memoization top se neeche recurse karta hai. Is order ko tod do — row 3 ko row 2 se pehle fill karo — toh tum khali boxes read karoge: parent ki pehli "steel-manned mistake" visible ho gayi.

PICTURE. Dependency picture: row $i - 1$ se arrow (solid, "already done") row $i$ mein upar (fill ho raha hai), red X ke saath kisi bhi koshish par jo abhi-fill-nahi-hui cell ko read karne ki ho.

Ek picture mein summary

Sab ek saath: zero base row table ko seed karti hai; har cell max(skip, take) choose karta hai; "take" item ke weight se upar-aur-left hop karta hai aur uski value add karta hai; guard hop ko block karta hai jab item zyada heavy ho; rows top-to-bottom fill hoti hain; corner answer $5$ hold karta hai.

Recall Feynman: plain words mein pura walkthrough

Ek boxes ka grid imagine karo. Top row sab zeros hai — "koi items nahi, koi value nahi, done." Ab ek ek row neeche jao. Har box ke liye ek question poochho: "Is row par item — kya main use grab karun ya chodun?" Chodna matlab "mujhse seedha upar wala box copy karo." Grab karna matlab "ek row upar jao, phir jitna yeh item weigh karta hai utne left slide karo, wahan jo bhi value likhi ho le lo, aur upar se is item ki value add karo." Donon mein se jo bada number ho woh rakho. Agar item us room se zyada heavy hai jo tum pretend kar rahe ho ki hai, tum use grab nahi kar sakte — bas upar se copy karo. Kyunki har box sirf upar wali row dekhta hai, tumhe rows top se neeche fill karni chahiye, taaki jis row ko tum dekhte ho woh already finished ho. Jab last row ka last box fill ho jaata hai, woh number — bottom-right corner — best value hai jo pura bag hold kar sakta hai. Hamare items ke liye woh 5 hai.

Active recall

dp[i][c] cell ka words mein kya matlab hai?

First

i

items ko use karte hue best total value, jab bag zyada se zyada capacity

c

hold kare.

Puri top row dp[0][c] ko 0 kyun set kiya jaata hai?

Zero items allowed hone par bag mein daalne ke liye kuch nahi, toh best value har capacity ke liye 0 hai — yeh table ko seed karta hai.

dp[i][c] = max(skip, take) mein "take" term kya hai?

v_{i} + d p [i - 1] [c - w_{i}]

— item

i

ki value grab karo, phir earlier items ke saath leftover room

c - w_{i}

ke liye best answer use karo.

Take branch se pehle if w_i <= c guard kyun lagana zaroori hai?

Warna

c - w_{i}

negative hoga — negative room wala bag, ek nonsense state aur out-of-bounds index.

Hamare example mein dp[3][4] kya hai aur yeh tie kyun hai?

5 — item 3 akele 5 deta hai, aur items 1+2 bhi 5 dete hain, toh max either way 5 rakhta hai.

Table top row se bottom row fill kyun karo?

Har cell sirf upar wali row se padta hai, toh woh row pehle fully computed honi chahiye (dependencies before use).

Connections

Tabulation (bottom-up DP) — iterative (index 3.7.8) — woh parent jise yeh page pictures mein derive karta hai
0-1 Knapsack — woh problem jo humne cell by cell fill ki
Optimal Substructure — kyun "best whole = best of sub-answers" yahan legal hai
Overlapping Subproblems — kyun table mein answers likhna payoff karta hai
Recurrence Relations — take/skip formula ki math
Space Optimization in DP — is 2D grid ko ek row mein collapse karo (phir capacity high→low iterate karo)
Memoization (top-down DP) — wohi recurrence, reverse order mein fill ki

Visual walkthrough — Tabulation (bottom-up DP) — iterative