Visual walkthrough — Dynamic programming — overlapping subproblems, optimal substructure

3.7.6 · D2 · Coding › Algorithm Paradigms › Dynamic programming — overlapping subproblems, optimal subst

Yeh parent topic ka visual companion hai. Hum bilkul zero se shuru karte hain: aapko bas itna pata hona chahiye ki "do numbers jodna" kya hota hai aur ek aisi recipe kya hoti hai jo khud ko call kare (ek quick refresher Recursion ke liye helpful hai).

Step 1 — "Ek subproblem" dikhta kaisa hai

KYA HAI. Hamara running example Fibonacci sequence hai. Yeh ek rule se define hota hai: $F(n)=F(n-1)+F(n-2)$

Hum ise use karne se pehle har symbol ko samjhte hain:

• $F$ ek machine hai: aap isme ek whole number $n$ daalo, yeh ek number wapas deta hai.
• $n$ input hai — "aapko kaun sa Fibonacci number chahiye?"
• $F(n-1)$ aur $F(n-2)$ woh do chhote sawaal hain jo machine ko bada sawal answer karne ke liye poochhne padte hain. Yeh chhote sawaal hi subproblems hain.
• $+$ kehta hai: do chhote answers ko jodke combine karo.

Hume base cases bhi chahiye — woh sabse chhote sawaal jo machine bina kuch pooche turant answer kar sakti hai: $F(0)=0,F(1)=1$

PEHLE YEH KYU DEFINE KAREN. Aap "repeated work" ki baat tab tak nahi kar sakte jab tak aap ek unit of work — ek input par $F$ ka ek call — ko point out na kar sako. Woh single box hi neeche ki har cheez ka atom hai.

PICTURE. Neeche, ek call ko uske input ke label wale box ki tarah draw kiya gaya hai. Arrow ka matlab hai "yeh box us box se sawal poochh raha hai."

Step 2 — Poora recursion tree grow karo (waste ko aate dekhte hain)

KYA HAI. Top sawal $F(5)$ lo aur tab tak rule apply karte raho jab tak har branch ek base case ($F(0)$ ya $F(1)$) tak na pahunch jaaye. Har box do children sprout karta hai: uska $F(n-1)$ aur $F(n-2)$.

KYU. Hum total work count karna chahte hain. Total work = tree mein boxes ki total sankhya, kyunki har box ek addition karta hai. Toh poora tree draw karna zaroori hai.

PICTURE. Tree dekho. Ab repeats dhundho: $F(3)$ kitne alag boxes mein likha hai? $F(2)$ mein? Colour-coded neeche — same sawal alag branches par fresh se poochha ja raha hai. Koi kuch yaad nahi rakhta.

Yahi repeated boxes hain jo parent note mein bataye gaye overlapping subproblems hain. Yeh dushman hain. (Yeh Divide and Conquer se alag hai, jahan har box ek alag sawal hota hai aur kuch repeat nahi hota.)

Step 3 — Waste measure karo: kyun tree $O(2^n)$ hai

KYA HAI. Boxes ko level ke hisaab se gino (top se doori).

• Level 0: $1$ box ($F(5)$).
• Level 1: $2$ boxes.
• Level 2: $4$ tak boxes.
• Level $k$: $2^k$ tak boxes.

YEH TOOL KYU — do ki powers. Har box do children banata hai, toh population har level neeche jaane par double hoti hai. Jab bhi koi quantity har step par double ho, uski size describe karne ka seedha tarika power of two, $2^k$ hai. Isliye hum $2^n$ use karte hain naa ki, $n^2$: doubling exponential growth ki pehchaan hai.

Total boxes $\approx 1+2+4+\cdots +2^n\approx 2^{n+1}$, jise hum ==$O(2^n)$== likhte hain (parent ka Time Complexity Analysis "big-O" = "se zyada fast nahi badhta").

PICTURE. Har level ek bar ki tarah draw hua; neeche jaate bar ki length double hoti hai. Total area hi wasted work hai.

Step 4 — Key observation: KITNE distinct sawaal hote hain?

KYA HAI. Tree mein $\sim 2^n$ boxes hain — lekin isme appear hone wale distinct inputs list karo: $F(0),F(1),F(2),F(3),F(4),F(5)$ $F(5)$ ke liye yeh sirf 6 alag sawaal hain. Generally, $F(n)$ ke liye exactly $n+1$ distinct inputs hain: $0,1,2,\dots ,n$.

YEH POORA GAME KYU HAI. Tree itna bada hai kyunki distinct sawaal baar baar pooche jaate hain. Lekin genuinely alag sawaal sirf $n$ ke aas paas hain. Agar hum har alag sawal ek baar answer karke reuse kar sakein, toh total work $2^n$ ki jagah $n$ ke karib hoga.

PICTURE. Left par messy tree ko sirf inputs $0$ se $n$ ki ek chhoti number line par squeeze kiya gaya hai. Kaafi tree boxes ek hi tick par collapse ho jaate hain.

Step 5 — Sticky-note (memoization) lagao aur branches ko marte dekho

KYA HAI. Ek table memo add karo (ek shelf of sticky notes, input ke hisaab se indexed). Har call ke liye naya rule:

1. Agar $n$ ka answer shelf par pehle se hai, toh wapas de do — recurse mat karo.
2. Warna ek baar compute karo, shelf par likho, phir return karo.

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]   # <-- sticky note: reuse, recompute mat karo
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Line by line:

• if n < 2: return n — base cases $F(0)=0,F(1)=1$, turant answer.
• if n in memo: return memo[n] — yahi toh poora point hai. Koi bhi sawal doosri baar poochha jaaye, uska poora subtree skip ho jaata hai.
• memo[n] = ... — ek baar solve karo, answer record karo.

KYU. Step 2 mein doosre $F(3)$, doosre/teesre $F(2)$ etc. ki branches pure repetition thi. Sticky-note check un repeated branches ko prune karke ek single lookup box mein badal deta hai. (Top-down vs bottom-up split ke liye Memoization vs Tabulation dekho.)

PICTURE. Wahi $F(5)$ tree, lekin pehli baar compute hone ke baad har box grey ho jaata hai aur ek one-step lookup se replace ho jaata hai. Mota exponential tree ek patli chain mein deflate ho jaata hai.

Step 6 — Dobara gino: multiplication formula niklata hai

KYA HAI. Memoization ke baad, har distinct input exactly ek baar compute hota hai. Toh: $\text{Time}=\underset{\text{Step 4}}{\underbrace{(\#\text{distinct subproblems})}}\times \underset{\text{ek }+\text{, yaani }O(1)}{\underbrace{(\text{work per subproblem})}}$

Fibonacci mein plug karo:

• $\#\text{distinct subproblems}=n+1\approx n$
• work per subproblem $=O(1)$ (ek addition + ek shelf write)

$\text{Time}=n\times O(1)=\boxed{O(n)}$

KYU ek product, sum nahi? Kyunki dono quantities independent hain: kitne alag kaam hain, times har kaam kitni der leta hai. Yeh har DP ka master formula hai — Fibonacci, Knapsack Problem ($nW$ kaam), Longest Common Subsequence ($nm$ kaam), yahan tak ki Bellman-Ford ($VE$ relaxations). Do factors badlo, kisi bhi DP ki cost mil jaayegi.

PICTURE. Ek grid: columns = distinct subproblems, har ek cell; har cell ke andar ek chhoti clock = work per cell. Total time = har cell ek baar bharna = (columns) × (per-cell work).

Step 7 — Degenerate / edge cases (kabhi skip mat karo)

KYA HAI AUR KYU. Ek derivation tab hi trustworthy hoti hai jab woh extremes mein bhi kaam kare.

• $n=0$ ya $n=1$ (base cases). Tree ek single box hai; overlap karne ke liye kuch nahi hai. Naive aur DP dono $O(1)$ cost karte hain. Memoization yahan na tez hai na slow — bas harmless hai. Seekh: overlap tab hi aata hai jab tree itna deep ho ki woh khud par wapas branch kar sake.
• Koi overlap NA ho (jaise Merge Sort, Divide and Conquer). Har distinct-subproblem count total-box count ke barabar hota hai. Step 4 ke dono numbers same hain, toh caching kuch nahi bachata aur sirf shelf space waste karta hai. DP yahan bekar hai.
• Koi optimal substructure NA ho (jaise graph mein sabse lamba simple path). Sub-answers combine karna galat hai kyunki sub-paths ek aisa node reuse kar sakte hain jo poora path pehle hi use kar chuka hai — toh shelf ek aisi value store karta hai jo reuse karna galat hai. Yahan memoization sirf useless nahi, galat answer deta hai.

PICTURE. Teen chhote trees side by side: (a) flat base case bina repeats ke, (b) ek Merge-Sort tree jahan sare leaves distinct hain, (c) ek path graph jahan sub-answer reuse karne par ek node double-count ho jaata hai — red ✗ se marked.

Ek-picture summary

Upar ki sab cheezein, ek single canvas par: left par mota $2^n$ tree, beech mein sticky-note shelf repeats collapse karte hue, aur right par patla $O(n)$ chain — neeche master formula print hua.

Connections

• Parent topic (Hinglish) — full treatment.
• Recursion — woh tree jahan se humne shuru kiya.
• Recursion Trees — Steps 2–3 ki counting technique.
• Memoization vs Tabulation — shelf, top-down aur bottom-up.
• Time Complexity Analysis — jahan se $O(2^n)$ aur $O(n)$ aate hain.
• Divide and Conquer — no-overlap edge case.
• Knapsack Problem, Longest Common Subsequence, Bellman-Ford — same master formula alag job counts ke saath.