2.7 Dynamic Programming

Deep Dive: Why DP Works (Not Just How)

Beginner tip: Dynamic Programming is just "smart brute force." Imagine calculating fib(50) -- the naive way recomputes fib(3) billions of times. DP saves each answer the first time and reuses it, turning billions of operations into just 50. If a problem has overlapping subproblems (same calculation repeated) and optimal substructure (big answer built from small answers), DP applies.

The Fibonacci Trap -- See Why Memoization Matters

Climbing Stairs for n=5 without memoization:

                  f(5)
                /      \
            f(4)        f(3)
           /    \       /   \
        f(3)   f(2)  f(2)  f(1)     <-- f(3) computed TWICE
       /   \
    f(2)  f(1)                        <-- f(2) computed THREE times

f(2) is computed 3 times. f(3) is computed 2 times. For n=50, this explodes to billions of calls. Adding a cache (memo) means each unique call happens exactly once: O(n).

The Coin Change Insight -- Building a DP Table

coins = [1, 5, 11], amount = 15. Build dp[i] = fewest coins for amount i:

amount:  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
dp:      0   1   2   3   4   1   2   3   4   5   2   1   2   3   4   3
                              ^                       ^
                              5=5(coin)               11=11(coin)

For dp[15]: try coin=1: dp[14]+1=5. Try coin=5: dp[10]+1=3. Try coin=11: dp[4]+1=5. Min = 3.

The recurrence in action: dp[i] = min(dp[i-coin] + 1) for each coin. Each cell builds on already-solved smaller amounts. That is the essence of DP.

The 2D DP Insight -- Edit Distance

Convert "horse" to "ros". Fill dp[i][j] = min ops for word1[:i] -> word2[:j]:

      ""  r  o  s
  ""   0  1  2  3
  h    1  1  2  3
  o    2  2  1  2
  r    3  2  2  2
  s    4  3  3  2
  e    5  4  4  3   <-- ANSWER: 3 operations

How to read the table: dp[2][2]=1 means "ho"->"ro" takes 1 op (replace h->r). Each cell looks at three neighbors: left (insert), above (delete), diagonal (replace/match).

DP is Just Smart Brute Force

Brute Force: try ALL possible choices (exponential)
Memoization: try all choices BUT remember results (polynomial)
Tabulation: fill table bottom-up (same complexity, no recursion overhead)

DP does not skip any possibilities. It explores everything, but never recomputes.

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About DP

What Is DP?

DP = Recursion + Memoization = avoid recomputing overlapping subproblems.

The DP Litmus Test

A problem is a DP problem if it has BOTH:

1. Overlapping subproblems: The same sub-computation appears multiple times
2. Optimal substructure: The optimal solution builds from optimal sub-solutions

The 4-Step DP Framework (Use This Every Time)

1. DEFINE STATE: What does dp[i] (or dp[i][j]) represent?
   -> One clear English sentence. If you can't state it, you can't solve it.

2. RECURRENCE: How does dp[i] relate to smaller states?
   -> "dp[i] = ...dp[i-1]... or ...dp[i-2]..." etc.

3. BASE CASE: What is dp[0]? dp[1]? dp[0][0]?
   -> The trivial case where the answer is obvious.

4. ORDER: Which direction do I fill the table?
   -> Bottom-up: small -> large. Top-down: large -> small + memo.

Top-Down vs Bottom-Up

TOP-DOWN (Memoization):
  Write recursive solution first. Add a cache (dict/array).
  Easier to think about. Slightly slower due to recursion overhead.

BOTTOM-UP (Tabulation):
  Fill a table iteratively from base cases upward.
  Faster (no recursion). Harder to figure out the order.

Tip: Always START with top-down. Convert to bottom-up if needed.

DP Categories: Recognize the Type

Type	State	Signal	Example
1D	dp[i]	"up to index i"	Climbing Stairs, House Robber
2D String	dp[i][j]	Two strings, match/edit	LCS, Edit Distance
2D Grid	dp[r][c]	Grid traversal	Unique Paths, Min Path Sum
Knapsack	dp[i][w]	"Choose items with budget"	Coin Change, Partition Equal Subset
Interval	dp[i][j]	"Solve for range [i..j]"	Burst Balloons, MCM

The Knapsack Family (Shows Up Everywhere)

0/1 Knapsack: each item used at most once
  -> Partition Equal Subset Sum, Target Sum

Unbounded Knapsack: each item unlimited uses
  -> Coin Change, Rod Cutting

Bounded Knapsack: each item has a limit
  -> Less common in interviews

Key insight: "Can I make target T from these numbers?" = Knapsack

When You See a Problem, Think

1. "How many ways to...?" / "Minimum cost to..." / "Is it possible?" -> Likely DP
2. Can I define a STATE that captures "where I am" in the problem?
3. Can I write dp[i] = something involving dp[i-1], dp[i-2], etc.?
4. Check: are there overlapping subproblems? (Draw recursion tree)
5. If no overlap -> Greedy or Backtracking instead

Common Mistakes

• Vague state definition -- if you can't write dp[i] = "..." in English, restart
• Wrong base case -- trace dp[0] and dp[1] manually

---

The DAG of Subproblems (Why Bottom-Up Order Works)

DP is just a topological sort of a dependency graph between subproblems. If you can draw which dp[i] cell depends on which other dp[j] cells, you have the algorithm.

For Coin Change with coins = [1, 5, 11], amount = 5:

graph TD
  D5["dp[5]"] -- "coin 1" --> D4["dp[4]"]
  D5 -- "coin 5" --> D0["dp[0] = 0"]
  D4 -- "coin 1" --> D3["dp[3]"]
  D3 -- "coin 1" --> D2["dp[2]"]
  D2 -- "coin 1" --> D1["dp[1]"]
  D1 -- "coin 1" --> D0
  classDef base fill:#dcfce7,stroke:#16a34a,color:#166534
  class D0 base

Every arrow points from a state to a smaller state it depends on. Since the graph is acyclic and every dependency points "left", we can safely fill the array from dp[0] to dp[5] in a single pass.

dp[5]                    each coin gives one possible "previous" subproblem
 ├── (coin 1) dp[4]      we tried coin 1, 4 left
 ├── (coin 5) dp[0]      we tried coin 5, 0 left  <-- base case
 └── (coin 11) (skip)    coin too large

dp[4] depends on dp[3]   (coin 1)
dp[3] depends on dp[2]   (coin 1)
dp[2] depends on dp[1]   (coin 1)
dp[1] depends on dp[0]   (coin 1)
dp[0] = 0                base case

The rule: if the dependency graph is a DAG (no cycles, every dependency is on a smaller index), you can fill the table in topological order — i.e. for i in range(0, amount + 1). If you ever find yourself wanting dp[i] to depend on dp[i+1], your state is wrong.

📚 MIT 6.006 calls this the SRTBOT framework: Subproblems → Relate → Topological order → Base cases → Original problem → Time. Lecture 15 of the Spring 2020 course is the most rigorous free DP explanation you'll find.

---

Common Wrong Approaches (Learn From These)

Beginners overwhelmingly trip on two things. Recognise the symptoms early.

Wrong State Definition

For Partition Equal Subset Sum, beginners often write:

dp[i] = "the smallest difference between two subsets using items 0..i"

This seems right but the recurrence becomes a nightmare — you'd need to track every reachable sum. The correct state is boolean:

dp[i][s] = "can we make sum s using a subset of items 0..i?"

Symptom you got the state wrong: the recurrence has 3+ branches, or you're carrying a list/dict in dp[i] instead of a number/boolean.

Filling the Table in the Wrong Direction

For House Robber II (the circular version), beginners often write:

for i in range(n - 1, -1, -1):       # right-to-left
    dp[i] = max(dp[i + 1], dp[i + 2] + nums[i])  # depends on dp[i+1], dp[i+2]

This is fine if you initialise the right-edge base cases first. But most beginners then write dp[n] = dp[n+1] = 0 and read dp[0] as the answer — and forget that the standard 1D Robber is dp[i] = max(dp[i-1], dp[i-2] + nums[i]) filling left-to-right. Mixing directions in the same problem leads to off-by-one errors that take 30 minutes to debug.

The fix: always draw the dependency arrows first. If dp[i] depends on dp[i-1], fill left-to-right. If it depends on dp[i+1], fill right-to-left. Pick one direction per problem.

---

• Wrong order of iteration in bottom-up (depends on recurrence direction)
• Not considering space optimization: many 2D DPs only need 2 rows (or 1)

Problems

#	Problem	DP Type	Difficulty	Status
1	Climbing Stairs	1D	Easy	[ ]
2	House Robber	1D	Medium	[ ]
3	House Robber II	1D circular	Medium	[ ]
4	Coin Change	Unbounded Knapsack	Medium	[ ]
5	Longest Increasing Subsequence	1D + BS	Medium	[ ]
6	Longest Common Subsequence	2D String	Medium	[ ]
7	Word Break	1D + Set	Medium	[ ]
8	Unique Paths	2D Grid	Medium	[ ]
9	Decode Ways	1D	Medium	[ ]
10	Edit Distance	2D String	Medium	[ ]
11	Target Sum	0/1 Knapsack	Medium	[ ]
12	Interleaving String	2D	Medium	[ ]
13	Longest Palindromic Subsequence	2D Interval	Medium	[ ]
14	Partition Equal Subset Sum	0/1 Knapsack	Medium	[ ]
15	Burst Balloons	Interval DP	Hard	[ ]
16	Regular Expression Matching	2D	Hard	[ ]
17	Maximum Profit in Job Scheduling	DP + BS	Hard	[ ]

4-Step DP Framework

1. DEFINE STATE: What does dp[i] represent?
2. RECURRENCE: How does dp[i] relate to smaller states?
3. BASE CASE: What is dp[0] or dp[1]?
4. ORDER: Bottom-up or Top-down?

Notes