3.7.9 · D1DP problems — Fibonacci, coin change (count + min), 0 - 1 kn
Dynamic Programming ka matlab hai ek bade problem ko solve karna — pehle uske andar chupi hui
chhoti copies ko solve karke , phir har chhote answer ko ek baar likh lena taaki dobara compute
na karna pade. Parent note mein sab kuch — Fibonacci, coin change, knapsack — bas yahi ek trick
hai, alag-alag bhesh mein.
Parent note padhne se pehle, tumhe har wo symbol apna banana hoga jo wahan aata hai. Neeche, har
tool ko zero se build kiya gaya hai: pehle plain words mein, phir ek picture, phir reason ki yeh
topic uske bina kaam nahi kar sakta. Upar se neeche padho — har item upar wale par lean karta hai.
Definition Ek machine ki tarah functionJab hum F ( n ) F of n ". Yahan F machine ka naam hai,
aur n input hai jo tum usme daalte ho . Machine ek number wapas karta hai — uska output .
Example: F ( 5 ) F
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: har DP object — F ( n ) dp [ a ] dp [ i ] [ w ] F ( n )
Intuition Subscripts aur brackets — same idea haiw i weights [ i ] ek hi cheez hai: "i ek slot ki taraf point karte hain.
Ek index ek counting label hai — 0 , 1 , 2 , 3 , … kaunsi position se hai. Hum n i a w kisi whole
number ki jagah use karte hain jo abhi fix nahi hua hai.
Ek sequence bas numbers ki ek row hoti hai, har index par ek. Fibonacci ek sequence hai: position 0 0 1 1 2 1
n ≥ 2 n kam se kam 2 hai " — symbol ≥ greater than or equal to .c ≤ a c zyada se zyada a hai " — ≤ less than or equal to .
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: poora game yahi hai ki "position n
Ek array (Python ise list kehta hai) numbered boxes ki ek row hoti hai. dp = [0,1,1,2,3,5] mein
chhe boxes hain; dp[3] index 3 2 Counting 0 se shuru hoti hai ,
isliye dp[0] pehla box hai.
dp wahan hai jahan hum har chhote answer ko ek baar likhte hain aur rakh lete hain . Yeh likha
hua memory hi DP aur plain recursion mein farq karti hai. dp[a] = "target a dp[i][w] = "pehle i w
dp[i][w] mein DO brackets kyun hain
Ek bracket ek single row hai. Do brackets ek grid hai — rows aur columns dono. Knapsack mein row
i w
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: "answer store karo aur reuse karo" bina store karne ki jagah
ke bekar hai. Array hi "recursion + memory" mein memory hai .
Recursion tab hota hai jab ek machine ke instructions mein yeh ho: "…aur khatam karne ke liye, mujhe
hi dobara chhote input par run karo." F ( n ) = F ( n − 1 ) + F ( n − 2 ) F Recursion and Memoization dekho.
Ek base case wo input hota hai jo itna chhota ho ki machine seedha answer de sake, khud ko
call kiye bina. F ( 0 ) = 0 F ( 1 ) = 1 dp[0]=1 (coin count) aur dp[0]=0 (min coins) bhi base cases hain.
Common mistake Recursion bina base case keKyun theek lagta hai: rule "khud ko chhote par call karo" poora lagta hai.
Kyun galat hai: bina floor ke calls hamesha chhoti hoti rahti hain (n , n − 1 , n − 2 , … Fix: hamesha sabse chhote
inputs ko pehle haath se define karo.
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: "problem ko apni chhoti versions mein todo" hi recursion
hai. DP recursion hai jo yaad rakhti hai.
Memoization = recursion + ek notepad. Answer compute karne se pehle notepad check karo
(if n in memo). Agar wahan hai, reuse karo. Nahi hai toh compute karo aur likh lo . Yeh word
"memo" se aaya hai, yaani note-to-self. Tabulation se compare karne ke liye
Tabulation vs Memoization dekho.
Intuition Kyun notepad exponential ko linear bana deta haiMemory ke bina, machine F F ( 3 ) F ( 0 ) , F ( 1 ) , … , F ( n ) bilkul ek baar compute hoti hai — yeh n + 1 linear , na ki ≈ ϕ n Time and Space Complexity mein hai.
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: "har chhoti version ek baar solve karo, store karo, reuse karo"
memoization ki definition hai — "DP = recursion + memory" ka doosra adha.
ϕ ϕ ϕ ≈ 1.618 ϕ multiply hote hain, isliye n ≈ ϕ n
Θ ( ⋅ ) Θ ( n ) theta of n " — matlab "kaam ki matra n n Θ ( ϕ n ) multiply hota hai har baar jab n Time and Space Complexity mein hai.
ϕ n ϕ n ϕ n ϕ 3 = ϕ ⋅ ϕ ⋅ ϕ n exponent hai — repeated multiplications ka count.
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: yahi symbols hain jisse parent measure karta hai ki DP kaam aaya
ya nahi. Θ ( ϕ n ) → Θ ( n )
∞ float('inf') likhte hain. Hum unreachable amounts ko ∞ real answer automatically chhota ho aur min
min max min ( a , b ) chhota return karta hai; max ( a , b ) bada . min c ≤ a c sabse kam
coins chahta hai (min sabse zyada value chahta hai (max
+= operator
dp[a] += dp[a-c] shorthand hai dp[a] = dp[a] + dp[a-c] ka — "jo pehle se hai usme yeh add karo. "
Coin-count tarike ikattha karta hai, isliye replace ki jagah add karta hai.
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: parent mein har recurrence ek min max + =
Ek subset items ka koi bhi selection hai — kuch lo, baaki chhod do. { A , B , C } { } { A } { A , C } { A , B , C }
0/1 knapsack ka matlab hai har item 0 baar ya 1 baar liya jata hai — ek yes/no switch, kabhi
do baar nahi. Unbounded se compare karo, jahan ek item baar baar reuse ho sakta hai (dekho
Unbounded Knapsack and Rod Cutting ). Yahi 0-ya-1 choice ki wajah se knapsack
pichli row dp[i-1] reference karta hai. Subset flavor
Subset Sum and Partition Problems ko bhi drive karta hai.
YEH TOPIC ISKE BINA KAAM KYUN NAHI KARTA: "value maximize karte hue ek subset chuno" knapsack ka statement
hai, aur 0/1 constraint wo ek detail hai jo ise coin change se alag banati hai.
Definition Optimal substructurePoore ka best answer uske parts ke best answers se banta hai. Agar amount 6 banane ka best tarika coin 3 par
khatam hota hai, toh bacha hua amount 3 bhi best solve hona chahiye.
Definition Overlapping subproblemsWahi ek chhota problem baar baar aata hai (jaise F ( 3 )
Intuition Dono hone chahiye — warna DP ki zarurat nahiOverlap nahi ⇒ kuch reuse karne ko nahi ⇒ plain divide-and-conquer kaafi hai. Optimal substructure nahi ⇒
chhote answers se bade nahi bana sakte ⇒ DP ki recurrence invalid hai. DP bilkul wahan rehta hai jahan
dono sach hain. (Yeh Greedy Algorithms ke saath fence-line bhi hai, jo har combination check kiye bina
local best commit kar leta hai.)
F ( n ) Input n F
Array counting kahan se shuru hoti hai? Index 0 dp[0] pehla box hai.
dp[i][w] mein do brackets kya hain?Ek grid: row i w
Recursion ek sentence mein kya hai? Ek machine jiske instructions usse chhote input par khud ko run karne ko kehte hain.
Base case kya hai aur yeh kyun hona chahiye? Sabse chhota input seedha answer diya jata hai; iske bina recursion kabhi nahi rukta.
Memoization recursion mein kya add karta hai? Ek notepad — har alag answer ek baar compute karo, store karo, reuse karo.
Memoized Fibonacci Θ ( n ) Θ ( ϕ n ) n + 1
≥ ≤ ≥ ≤
Unreachable amounts ko ∞ Taaki koi bhi real answer automatically chhota ho aur min
Coin-count ke liye dp[0]=1 kyun hai lekin min-coins ke liye dp[0]=0 kyun? 0 banane ka ek tarika hai (kuch mat lo) vs 0 banane mein zero coins chahiye.
0/1 knapsack mein "0/1" ka kya matlab hai? Har item zero ya ek baar liya jata hai — kabhi reuse nahi.
DP apply karne ke liye kaunsi do conditions honi chahiye? Optimal substructure AUR overlapping subproblems.
