Dynamic programming — overlapping subproblems, optimal substructure: Foundations

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

Is page par assume kiya gaya hai ki tumne kuch nahi dekha. Parent note Dynamic Programming padhne se pehle, tumhe neeche diya hua chota sa alphabet fluently aana chahiye. Hum har symbol ko pichle symbol ke upar build karte hain.

0. "Subproblem" kya hota hai? (sab kuch ka atom)

Yahan har symbol ek word ke around ghoomta hai: subproblem.

Ise ek nesting doll ki tarah socho: badi doll (poora problem) ke andar choti identical dolls (subproblems) hoti hain. Jab tak tum problems ko is nazar se nahi dekhte, DP samajh nahi aayega.

Figure — Dynamic programming — overlapping subproblems, optimal substructure

Topic ko yeh kyun chahiye: neeche diye gaye baaki saare symbols subproblems ko naam dene, count karne, ya store karne ke tarike hain. Subproblem nahi, toh DP nahi.

1. Function-call symbol $F (n)$

Ek vending machine socho: button $n$ dabaao, ek answer nikalta hai.

Letter $F$ sirf ek label hai — hum ise $K$ , $fib$ , ya "the-answer-getter" bhi keh sakte hain.
Brackets ke andar ki cheez, $n$ , input hai — problem ki size ya state.

2. Recursion: ek machine jo khud ko call karti hai

Yahan " $+$ " kyun? Kyunki Fibonacci mein poora literally do chote answers ka sum hota hai. Alag problems alag tarah combine karti hain (baad mein $max$ dekhenge) — combining rule hi har DP ka dil hai.

Recursion ko ek tree jो neeche ki taraf badhta hai socho: upar ek call, choti calls mein split hoti hai, jo aur split hoti hain, jab tak har branch ek base case (leaf) tak nahi pahunch jaati.

3. Recursion tree ko padhna — jahan "overlap" dikhta hai

Phir se tree figure (s02) dekho. Har node jo $F (3)$ label se marked hai use dhundho. $F (5)$ ke tree mein, $F (3)$ do baar aata hai, $F (2)$ teen baar aata hai. Wahi repeats hain jiske liye DP exist karta hai.

Yeh gap — bahut saare nodes, thode distinct — hi woh exploitable waste hai. Detailed tree-counting Recursion Trees mein hai.

Topic ko yeh kyun chahiye: DP ka poora payoff hai "thode distinct wale solve karo, saare repeats skip karo." Jab tak repeats nahi dikhte, payoff nahi dikheга.

4. Big-O: woh symbol jo waste measure karta hai

Do runners socho:

$O (n)$ ek gentle ramp par chadhta hai.
Exponential growth ek near-vertical cliff par shoot karta hai.

5. "Sticky note": ek table / memo

Do symbols comfortably padhne ke liye:

$d p [i]$ — sticky notes ki ek 1-D row (Fibonacci yahi use karta hai).
$d p [i] [c]$ — ek 2-D grid, har input ke liye ek axis. Knapsack $i$ = item index aur $c$ = capacity use karta hai.

$d p [i] [c]$ ko ek spreadsheet socho: rows items hain, columns capacities hain, har cell ek stored answer hai.

Topic ko yeh kyun chahiye: table woh memory hai jo plain recursion ko DP mein upgrade karti hai. Iske bina, §3 ke repeats recompute hote hain; iske saath, har distinct doll ek baar solve hoti hai.

6. $max$ symbol aur "optimal"

Recurrence se pehle, iske symbols se milte hain. Knapsack Problem mein hmare paas items ki ek list hai; item number $i$ ke paas hai:

$v_{i}$ = item $i$ ki value (yeh kitna worth hai),
$w_{i}$ = item $i$ ka weight (yeh kitni jagah leta hai),
$c$ = backpack mein abhi remaining capacity.

Greedy Algorithms se contrast karo (jo locally best option ek baar le leta hai aur kabhi reconsider nahi karta) aur Divide and Conquer se (jiske subproblems sab distinct hain, toh sticky notes help nahi karte). Doosre classic optimal-substructure problems: Longest Common Subsequence, Bellman-Ford.

Prerequisite map

Har arrow ka matlab hai "right box samajhne se pehle left box chahiye." Topic sabse neeche hai kyunki yeh sab foundations ko fuse karta hai.

Equipment checklist

Right side cover karo aur parent note kholne se pehle answer bolo.

F (n)

ka ek sentence mein matlab kya hai?

Jab input ki size/value

n

ho tab problem ka answer — ek machine jise tum

n

dete ho aur ek answer milta hai.

Fibonacci ke

F

ka domain kya hai?

Non-negative integers

n \in N_{0} = {0, 1, 2, \dots}

— na fractions, na negatives.

Subproblem kya hota hai?

Wahi problem ki ek choti copy (ek choti nesting doll).

Base case kya hai aur yeh kyun zaroori hai?

Sabse chota input jiska answer directly pata ho; iske bina recursion kabhi nahi rukti (aur yeh

n

ko zero se neeche jaane se rokti hai).

Recursion tree mein "overlapping subproblems" kaisa dikhta hai?

Wahi node label tree mein ek se zyada jagah dikhna.

F (5)

ke distinct subproblems, aur node count kaise badhta hai?

Sirf

n + 1 = 6

distinct, par total node count

Θ (φ^{n}) \approx 1.61 8^{n}

ki tarah badhta hai — exponential.

O (g (n))

formally kya matlab hai?

Running time ek fixed multiple ke neeche rehti hai yardstick function

g (n)

ke, jab

n

kaafi bada ho —

g

ek ceiling hai.

d p [i] [c]

kya hai?

2-D table ka ek cell jo

i

aur

c

se indexed subproblem ka answer store karta hai.

Memoization vs tabulation ek ek line mein?

Memoization = top-down recursion jo pehle table check karta hai (lazy); tabulation = bottom-up loop jo sabse chote pehle fill karta hai (eager).

max (a, b)

kya karta hai, aur DP mein kab use hota hai?

a

aur

b

mein se bada return karta hai; jab problem best option choose karti hai tab use hota hai (jaise knapsack mein take-or-skip).

Knapsack mein

v_{i}

w_{i}

c

, aur

K (i, c)

kya hain?

v_{i}

= item

i

ki value;

w_{i}

= uska weight;

c

= bacha hua capacity;

K (i, c)

= items

1.. i

use karke best value jab room

c

ho.

Knapsack recurrence teen cases mein kyun split hota hai?

i = 0

(koi item nahi),

w_{i} > c

(item fit nahi hota — skip, negative index se bachata hai), aur

w_{i} \leq c

(take/skip mein se better choose karo) handle karne ke liye.

Optimal substructure plain words mein batao.

Poore ka best answer uske parts ke best answers se build hota hai.

Combining operator kabhi

+

aur kabhi

max

kyun hota hai?

Yeh match karta hai jo problem poochti hai — Fibonacci do answers add karta hai, knapsack do options mein se best pick karta hai.

Master formula Time = (#subproblems)×(work each) kahan se aata hai?

Har table cell ki fill-cost sum karne se; agar har cell same cost le, toh sum ban jaata hai count × work-per-cell.

Connections

Recursion — woh machine jis par DP bana hai.
Recursion Trees — jahan overlap visible hota hai.
Time Complexity Analysis — $O (\cdot)$ ka matlab.
Memoization vs Tabulation — table fill karne ke do styles.
Divide and Conquer — disjoint subproblems, toh caching help nahi karta.
Greedy Algorithms — ek baar commit karta hai, kabhi reconsider nahi karta.
Knapsack Problem, Longest Common Subsequence, Bellman-Ford — optimal-substructure classics.