Dynamic programming — overlapping subproblems, optimal substructure: Question bank

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

Do words jo tumhe baar baar chahiye honge:

Subproblem — usi sawaal ka ek chhota version (jaise $F (3)$ , $F (5)$ ka subproblem hai).
Recurrence — wo formula jo ek bade answer ko chhote answers ke terms mein express karta hai.

Both properties, ek saath restated: overlapping subproblems ka matlab hai "wahi chhota sawaal ek se zyada baar poochha jaata hai"; optimal substructure ka matlab hai "sabse accha bada answer sabse acche chhote answers se banta hai."

True ya false — justify karo

Har recursive function memoization se benefit karta hai.

False — memoization tabhi help karta hai jab subproblems overlap karein; Merge Sort ke subproblems sab distinct hote hain, isliye cache sirf memory add karta hai aur kuch save nahi karta.

Agar kisi problem mein optimal substructure hai, to automatically overlapping subproblems bhi hote hain.

False — ye dono independent hain. Sorted array par Binary search mein optimal substructure hai (answer ek recursively-searched half mein rehta hai) lekin har half ek fresh, non-repeating subproblem hai, isliye koi overlap nahi.

Agar kisi problem mein overlapping subproblems hain, to DP hamesha correct answer dega.

False — overlap sirf caching ko worth it banata hai; optimal substructure ke bina cached sub-answers ek correct whole mein combine nahi hote (dekho: longest simple path).

Tabulation aur memoization ki time complexity hamesha same hoti hai.

True big-O sense mein — dono har distinct subproblem ko ek baar solve karte hain, isliye dono

(# subproblems) \times (work each)

hit karte hain; ye constants aur recursion overhead mein differ karte hain, asymptotics mein nahi.

Memoization same problem ke liye tabulation se asymptotically slower ho sakta hai.

False time ke liye — dono

(# distinct subproblems) \times (work)

hain. Memoization call-stack overhead add kar sakta hai (ek constant factor), aur tabulation un subproblems par time waste kar sakta hai jo memoization skip kar deta, lekin big-O ceiling identical hai.

DP hamesha plain recursion se kam memory use karta hai.

False — DP ek table add karta hai. Ye memory ko time ke liye trade karta hai; agar kisi problem mein overlap nahi hai to memory kharchta hai aur kuch nahi milta.

Distinct subproblems ki count, na ki recursive calls ki count, DP time set karti hai.

True — table guarantee karta hai ki har distinct subproblem exactly ek baar compute ho, isliye distinct-subproblem count (times work each) poora cost hai. Dekho Time Complexity Analysis.

Bottom-up tabulation recurrence ke baare mein sochne ki zarurat khatam kar deta hai.

False — recurrence hi fill rule hai; tabulation sirf ise recursion ki jagah dependency-respecting order mein evaluate karta hai.

Greedy aur DP problems ki same class solve karte hain.

False — Greedy ko zyada strong greedy-choice property chahiye (ek locally-best choice provably globally safe hai); DP ko sirf optimal substructure chahiye, jo weaker hai aur strictly zyada problems cover karta hai. Dekho Greedy Algorithms.

Spot the error

"0/1 Knapsack: bas items ko value-to-weight ratio se sort karo aur best wale lo jab tak bhar na jaye."

Ye fractional knapsack greedy hai; 0/1 mein tum item ko split nahi kar sakte, isliye ek high-ratio item ek better whole-item combination ko block kar sakta hai — ye galat total de sakta hai.

"Meri tabulation dp[i-1][c] read karti hai lekin main i ko n se 1 tak loop karta hoon."

Galat fill order — row

i - 1

ko row

i

read hone se pehle fill karna zaroori hai, isliye i increase hona chahiye (ya poori dependency direction respect honi chahiye). Dekho Memoization vs Tabulation.

"Do nodes ke beech longest simple path: main endpoint pair par shortest path ki tarah memoize karoonga."

Koi optimal substructure nahi — ek longest sub-path us node ko reuse karna chahega jo outer path pehle se use kar chuka hai, isliye sub-answers combine karne se ek invalid (node-repeating) path aur galat length aa sakti hai.

"def fib(n, memo={}) ke saath Fibonacci — mutable default ek clean private cache hai."

Trap: dict ek baar create hoti hai aur har top-level call mein share hoti hai, isliye state calls ke beech leak hoti hai. Pure Fib ke liye correct behavior hai, lekin ek common bug source hai; prefer karo memo explicitly pass karna ya None use karna.

"Knapsack base case: maine dp[0][c] uninitialized chhod diya kyunki zero items obviously zero dete hain."

Value zero hai, lekin agar array

0

se initialize nahi hai to pehla row read (dp[i-1] at

i = 1

) garbage hai — base case sirf "obvious" nahi hona chahiye, use materialize karna zaroori hai.

"Maine memory bachane ke liye knapsack mein sirf (i) par memoize kiya, kyunki c derivable hai."

Galat key — wahi item index

i

alag alag remaining capacities

c

ke saath reach hota hai; c drop karne se distinct subproblems collapse hote hain aur answers corrupt hote hain. State poori

(i, c)

pair hai.

"Mera recurrence sahi hai, isliye koi bhi loop order jo poora table fill kare kaam karega."

False — ek correct recurrence ko bhi reads ki zarurat hai ki wo apni dependencies ke likhe jaane ke baad ho; order ek alag correctness condition hai formula se alag.

Why questions

Kisi DP answer par trust karne se pehle optimal substructure verify karna kyun zaroori hai?

Kyunki iske bina, optimal sub-answers combine karna invalid ya suboptimal ho sakta hai, isliye algorithm confidently galat number return karta hai — code theek se run karta hai aur jhooth bolta hai.

Fibonacci DP ke under

O (2^{n})

O (n)

par kyun aa jaata hai?

Naive tree mein

\approx 2^{n}

nodes hote hain kyunki har call bina memory ke kaam dobara spawn karta hai; caching ise

n

distinct subproblems tak collapse kar deta hai, har ek ek baar done. Dekho Recursion Trees.

Merge Sort DP kyun nahi hai, bawajood iske ki recursive hai?

Iske subproblems (do halves) kabhi repeat nahi hote — ye disjoint hain — isliye cache karne ke liye kuch nahi hai; DP ke liye overlap zaroori hai taaki fayda ho.

Knapsack ka time

W

(capacity) par kyun depend karta hai, sirf

n

(item count) par nahi?

Subproblem state

(i, c)

pair hai jahan

c

0.. W

range karta hai, jo

n \cdot W

distinct states deta hai — capacity problem ki ek genuine dimension hai, isliye wo cost mein enter karta hai.

Bellman-Ford shortest paths compute kar sakta hai lekin same idea se longest simple paths kyun nahi?

Shortest paths mein optimal substructure hai (ek shortest path ke pieces shortest hote hain); longest simple paths mein nahi, kyunki sub-paths freely nodes reuse nahi kar sakte, isliye sub-answers compose nahi hote.

Kuch inputs par memoization tabulation se kam subproblems kyun solve karta hai?

Memoization lazy hai — wo sirf un states ko expand karta hai jo top query actually reach karta hai; tabulation poora table eagerly fill karta hai, including those states jinhein koi query need nahi karti.

"DP = recursion + remembering" poori baat kyun nahi hai?

Remembering tabhi help karta hai jab wahi sawaal dobara aayein (overlap) aur tabhi sahi rehta hai jab answers compose ho sakein (optimal substructure); koi bhi miss karo aur remembering useless ya galat hai.

Edge cases

Knapsack recurrence kya karta hai jab kisi item ka weight remaining capacity se zyada ho (

w_{i} > c

Ye "skip" branch

K (i - 1, c)

par fall karta hai — item simply nahi liya ja sakta, isliye uski value option kabhi consider nahi hoti.

F (0)

aur

F (1)

kya hai, aur loop shuru hone se pehle dono ko seed karna kyun zaroori hai?

F (0) = 0

F (1) = 1

; recurrence do prior terms read karta hai, isliye ek single base case pehle real step ko ek missing operand ke saath chhod deta hai.

Tabulation mein, knapsack mein capacity

W = 0

ho to kya hoga?

Har

d p [i] [0] = 0

— koi room nahi matlab koi items nahi — aur loops phir bhi harmlessly run karte hain,

0

return karte hain; degenerate case base row/column se handle hota hai, kisi special branch se nahi.

Agar kisi DP problem mein exactly ek subproblem depth ho (recursion ki zarurat nahi)?

Tab koi overlap nahi aur kuch build up karne ki zarurat nahi — ye ek direct computation hai, aur ise DP table mein wrap karna pure overhead hai.

Jaise jaise overlap zero ke paas jaata hai (sab subproblems distinct), memoization ka benefit kya hota hai?

Cache kabhi hit nahi score karta, isliye runtime plain recursion jaisa ho jaata hai jabki memory badhti hai — classic "mera memoized Divide and Conquer faster kyun nahi hai?" trap.

Bahut bade

n

ke liye, Fibonacci tabulation ka space

O (1)

kyun reduce ho sakta hai?

Har term ko sirf pichle do chahiye, isliye tum poori array ki jagah do rolling variables rakh sakte ho — table ki width nahi, uski history hai jo actually depend karti hai.