Dynamic programming — overlapping subproblems, optimal substructure

3.7.6 · Coding › Algorithm Paradigms

DP exist kyun karta hai?

Plain recursion aksar same cheez ko exponentially zyada baar recompute karta hai. DP usi waste ko khatam karne ke liye exist karta hai.

DO properties (DP use karne se pehle DONO verify karna ZAROORI hai)

Recursion ko DP mein kaise badlein — do styles

Speedup ko first principles se derive karna

Worked Example 1 — Fibonacci, teen tarike se

Naive recursion ($O(2^n)$):

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Memoization (top-down):

def fib(n, memo={}):
    if n < 2: return n
    if n in memo: return memo[n]      # reuse — kills overlap
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Yeh step kyun? if n in memo check ek exponential tree ko ek linear chain mein convert kar deta hai: har $F(k)$ ek baar compute hota hai, phir cache se serve hota hai.

Tabulation (bottom-up):

def fib(n):
    if n < 2: return n
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])   # smallest → largest
    return dp[n]

Yeh step kyun? Hum increasing $i$ mein fill karte hain taaki $dp[i-1],dp[i-2]$ pehle se computed hon — yahi ordering exactly "optimal substructure ko concrete banana" hai.

Worked Example 2 — 0/1 Knapsack (dono properties dikhate hue)

Items jinke weight $w_i$, value $v_i$ hai, capacity $W$ hai. Value maximize karo.

Recurrence derive karo. Item $i$ ko remaining capacity $c$ ke saath socho. Do choices hain:

1. Skip karo: best value hai $K(i-1,c)$.
2. Lo (sirf tab agar $w_i\le c$): $v_i$ gain karo + baaki ka best kam room ke saath: $v_i+K(i-1,c-w_i)$.

Yeh optimal substructure kyun hai? Items $\mathrm{1..}i$ ki best packing mein zaroori hai ki baaki bachi capacity ke liye $\mathrm{1..}i-1$ ki best packing ho — warna hum us better sub-packing ko swap karke poore ko improve kar sakte the. Overlap kyun hai? Kaafi alag item-prefixes same $(i,c)$ pair tak pahunchte hain.

def knapsack(w, v, W):
    n = len(w)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for c in range(W+1):
            dp[i][c] = dp[i-1][c]                       # skip
            if w[i-1] <= c:
                dp[i][c] = max(dp[i][c],
                               v[i-1] + dp[i-1][c-w[i-1]])  # take
    return dp[n][W]

Time $=n\cdot W$ subproblems $\times O(1)=O(nW)$.

Steel-manned mistakes

Flashcards

Connections

• Recursion — DP memory-augmented recursion hai.
• Divide and Conquer — subproblems disjoint hain (koi overlap nahi) → DP nahi.
• Greedy Algorithms — greedy-choice property chahiye; DP ko sirf optimal substructure chahiye.
• Memoization vs Tabulation
• Knapsack Problem, Longest Common Subsequence, Bellman-Ford
• Time Complexity Analysis
• Recursion Trees

Concept Map