Pattern 15: Dynamic Programming

Deep Dive: The 4-Step Framework Applied

House Robber: nums = [2, 7, 9, 3, 1]

Step 1 - STATE: dp[i] = max money from houses 0..i
Step 2 - RECURRENCE: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
         "Skip house i" vs "Rob house i (skip i-1)"
Step 3 - BASE: dp[0]=2, dp[1]=max(2,7)=7
Step 4 - ORDER: left to right

i=0: dp[0] = 2
i=1: dp[1] = max(2, 7) = 7    (rob house 1, skip house 0)
i=2: dp[2] = max(7, 2+9) = 11 (rob houses 0 and 2)
i=3: dp[3] = max(11, 7+3) = 11 (skip house 3)
i=4: dp[4] = max(11, 11+1) = 12 (rob houses 0, 2, 4)

Answer: 12

Space trick: You only need dp[i-1] and dp[i-2]. Replace the array with two variables: prev1, prev2.

---

Signal: "How many ways", "minimum cost", "maximum value", "is it possible" with overlapping subproblems Template: dp_1d() / dp_2d_strings() in templates.py

When to Use

• Optimization or counting with overlapping subproblems
• "Can I make target from these elements?"
• "Longest/shortest subsequence"
• Recursive solution has repeated states

The 4-Step Framework

1. DEFINE STATE: dp[i] = "..."
2. RECURRENCE: dp[i] = f(dp[i-1], dp[i-2], ...)
3. BASE CASE: dp[0] = ...
4. ORDER: Fill small -> large

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Climbing Stairs	Phase 2.7	8 min	[ ]
Coin Change	Phase 2.7	20 min	[ ]
Longest Common Subsequence	Phase 2.7	20 min	[ ]
Edit Distance	Phase 2.7	25 min	[ ]

New Practice Problems

Use these to drill DP recognition specifically — each one looks like it might be Greedy or Backtracking but is actually DP. Solve from LeetCode then mark below.

#	Problem	Why it's tricky	Difficulty	Time	Status
1	Maximal Square	Looks like a grid-traversal / BFS but is 2D DP dp[r][c] = side length of square ending here	Medium	25 min	[ ]
2	Best Time to Buy and Sell Stock with Cooldown	Greedy fails because of the cooldown — needs state machine DP	Medium	25 min	[ ]
3	Minimum Cost For Tickets	Looks like Greedy on intervals but the correct answer requires 1D DP over days	Medium	25 min	[ ]

Pattern Identification Drill (DP vs Greedy vs Backtracking)

For each of the three problems above, BEFORE coding, write down:

1. Why is this DP and not pure Greedy? (signal: optimal locally ≠ optimal globally)
2. Why is this DP and not pure Backtracking? (signal: overlapping subproblems exist)
3. What is the state? Express it in one English sentence.

If you can answer all three before coding, you have built the DP recognition reflex Phase 3 is meant to develop.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Number of ways to...", "Minimum cost to...", "Maximum profit / value if...", "Is it possible to..." — the four canonical DP question stems.
• "Decisions made step-by-step where past choices constrain future ones" AND those past choices can be summarised in a small state (an index, a remaining capacity, a last-used item).
• Constraints like n ≤ 1000 or n ≤ 5000 with no obvious greedy — points at O(n²) DP.
• "Longest / shortest subsequence" (note: subsequence, not subarray) — almost always 1D or 2D DP.
• "Match / edit / align / interleave two strings" — 2D DP indexed by (i, j) over the two strings.

Anti-signals (looks like this pattern, isn't)

• "Find any subset that sums to X" with n ≤ 25 — backtracking is faster (a DP table over 2^25 states is infeasible).
• "Local optimal = global optimal" provably (Activity Selection, Huffman coding, Interval Scheduling) — Greedy beats DP every time.
• "Longest / shortest contiguous subarray with property X" — usually Sliding Window or Two Pointers, not DP. (Subsequence ≠ subarray.)
• Constraints like n ≤ 10^6 — a DP table won't fit; look for Greedy, Math, or Sliding Window.