Dynamic programming — overlapping subproblems, optimal substructure

WHY does DP exist?

Plain recursion often recomputes the same thing exponentially many times. DP exists to kill that waste.

The TWO properties (you MUST verify both before using DP)

HOW to turn recursion into DP — two styles

Deriving the speedup from first principles

Figure — Dynamic programming — overlapping subproblems, optimal substructure

Worked Example 1 — Fibonacci, three ways

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]

Why this step? The if n in memo check converts an exponential tree into a linear chain: each $F(k)$ is computed once, then served from cache.

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]

Why this step? We fill in increasing $i$ so $dp[i-1], dp[i-2]$ are already computed — that ordering is exactly "optimal substructure made concrete."

Worked Example 2 — 0/1 Knapsack (showing both properties)

Items with weight $w_i$ , value $v_i$ , capacity $W$ . Maximize value.

Derive the recurrence. Consider item $i$ with remaining capacity $c$ . Two choices:

Skip it: best value is $K(i-1, c)$ .
Take it (only if $w_i \le c$ ): gain $v_i$ + best of the rest with less room: $v_i + K(i-1, c-w_i)$ .

Why is this optimal substructure? The best packing of items $1..i$ must contain a best packing of $1..i\!-\!1$ for whatever capacity is left — otherwise we could swap in the better sub-packing and improve the whole. Why overlapping? Many different item-prefixes hit the same $(i,c)$ pair.

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

Recall Feynman: explain it to a 12-year-old

Imagine homework where the same little math problem shows up 50 times. A lazy-but-smart kid solves it once, writes the answer on a sticky note, and just copies it the other 49 times. That's memoization. Tabulation is doing all the tiny problems first, in order, before the big one — like building Lego from the bottom blocks up. The trick only helps because (1) the same little problems keep repeating, and (2) the big answer is genuinely made of the little answers.

Flashcards

What are the two properties a problem needs for DP to apply?

Overlapping subproblems and optimal substructure.

Define overlapping subproblems.

When the recursive solution revisits the same subproblem multiple times.

Define optimal substructure.

When an optimal solution to the whole can be built from optimal solutions to its subproblems.

What's the difference between memoization and tabulation?

Memoization is top-down (recursion + cache, lazy); tabulation is bottom-up (iterative table fill, eager).

General formula for DP time complexity?

(number of distinct subproblems) × (work per subproblem).

Fibonacci: naive vs DP time complexity?

Naive

O(2^n)

vs DP

O(n)

Why doesn't Merge Sort benefit from DP?

Its subproblems are all distinct — there are no overlapping subproblems to cache.

Why does greedy fail for 0/1 knapsack but DP works?

0/1 knapsack lacks the greedy-choice property; DP only needs optimal substructure, which it has.

Give a problem with overlap but NO optimal substructure.

Longest simple path in a graph (sub-paths can't reuse nodes), so DP/memoization gives wrong answers.

What ordering rule must tabulation obey?

Fill subproblems in an order where every dependency is already computed before it's read.

0/1 Knapsack recurrence?

K(i,c)=max(K(i-1,c), v_i+K(i-1,c-w_i)) when w_i≤c, else K(i-1,c).

Time complexity of 0/1 knapsack DP?

O(nW), n items × W capacity subproblems.

Connections

Recursion — DP is memory-augmented recursion.
Divide and Conquer — subproblems are disjoint (no overlap) → not DP.
Greedy Algorithms — needs greedy-choice property; DP needs only optimal substructure.
Memoization vs Tabulation
Knapsack Problem, Longest Common Subsequence, Bellman-Ford
Time Complexity Analysis
Recursion Trees

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Dynamic Programming ka core idea bilkul simple hai: recursion + yaad rakhna. Jab tum koi problem recursion se solve karte ho aur wahi chhoti problem baar-baar repeat hoti hai (yeh hai overlapping subproblems), toh har baar use dobara solve karna pure waste hai. Fibonacci dekho — $F(5)$ nikalne mein $F(3)$ kai baar compute hota hai, aur tree exponential ban jaata hai, $O(2^n)$ . DP bolta hai: ek sticky note pe answer likh lo (cache/table), aur agli baar bas copy kar lo. Bas isse time $O(n)$ ho jaata hai.

Do cheezein zaroori hain. Pehli, optimal substructure — matlab bade problem ka best answer chhote problems ke best answers se banta hai. Yeh guarantee karta hai ki sub-answers jodna sahi hai. Doosri, overlapping subproblems — matlab same chhoti problem baar-baar aati hai, tabhi caching faydemand hai. Dono chahiye: bina substructure ke DP galat answer dega (jaise longest simple path), aur bina overlap ke (jaise Merge Sort) DP sirf extra memory khaayega, speed nahi badhegi.

Do styles hain. Memoization (top-down): normal recursion likho, par answer ko map/array mein store karo, aur compute se pehle check karo "kya pehle se hai?". Tabulation (bottom-up): table ko sabse chhoti problem se shuru karke upar tak bharo, aise order mein ki jab tumhe dp[i-1] chahiye toh woh pehle se ready ho. Yaad rakho: fill order recurrence ki dependency ko respect kare, warna galat answer aayega.

Ek important warning — greedy se dhokha mat khaana. Fractional knapsack mein greedy chalta hai, par 0/1 knapsack mein items tod nahi sakte, isliye greedy fail ho jaata hai aur DP ( $O(nW)$ ) lagana padta hai. Mnemonic simple: "OO" → DP OK (Overlapping + Optimal). Exam aur interviews dono mein yeh paradigm bahut aata hai, toh recurrence khud derive karna seekho, ratta mat maaro.

Dynamic programming — overlapping subproblems, optimal substructure

WHY does DP exist?

The TWO properties (you MUST verify both before using DP)

HOW to turn recursion into DP — two styles

Deriving the speedup from first principles

Worked Example 1 — Fibonacci, three ways

Worked Example 2 — 0/1 Knapsack (showing both properties)

Steel-manned mistakes

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections