Day 73 — Revision: Advanced DP

Revision day · advanced dynamic programming · blank-file recall

Tonight's goal: choose the weakest advanced-DP patterns, state the invariant before code, and pass the blank-file two-run gate.

Tonight's protocol

Use the revision rules from How to Run a Revision Day: blank file, no hints, invariant first, and only run one or run two counts.

0:00-0:04: Answer the warm-up MCQs below. If one feels shaky, mark that menu item as weak.
0:04-0:05: Pick your 3 weakest choices from the menu. The 2D-grid pair, Longest Common Subsequence plus Edit Distance, counts as one choice.
0:05-0:30: Choice 1. Open a blank file, say the invariant, brute force, state, transition, base case, answer location, then code with no hints.
0:30-0:55: Choice 2. Same rule: first or second run only. If it fails after two runs, stop and log the root cause.
0:55-1:20: Choice 3. If this choice is the 2D-grid pair, submit the weaker one and write the other recurrence from memory.
1:20-1:30: Compare only after the attempts. Encode one line per miss: WA: <root cause>.

The problem menu

Redo your 3 weakest from this menu from a blank file, no hints. The 2D-grid pair counts as one choice.

Problem	Pattern name	Invariant to say first
Longest Common Subsequence	2D DP: two strings, one grid	Match extends diagonal; mismatch keeps the better neighbor.
Edit Distance	Two-string DP: insert, delete, replace	Prefix edits are free on match, else one plus the cheapest operation.
Decode Ways	Counting DP with validity constraints	Only valid one- or two-digit chunks add ways.
Word Break	Segmentable prefixes	A true earlier prefix plus one dictionary word makes a later prefix true.
Burst Balloons	Interval DP: choose the last action	Pick the last balloon inside the interval so the two sides separate.

Warm-up MCQs

1. Which invariant is Longest Common Subsequence?

Source invariant: “When characters match, extend the diagonal: dp[i][j] = dp[i-1][j-1] + 1; otherwise take the better of dropping one character from either string.”

2. A match case sets dp[i][j] = 0. What broke?

3. Which Decode Ways move is allowed?

4. dp[0] stays false in Word Break. What fails?

5. Which decision separates Burst Balloons intervals?

6. Which pattern fills O(n²) states with O(n) choices?

Self-check gate

Pass tonight only if

For all 3 choices, you state the invariant before code, start from a blank file, and either pass on run one or two or log the exact miss.

Failure path: any failed problem goes into the next revision list with WA: <root cause>. If the failed item is the 2D-grid choice, keep both LCS and Edit Distance in the queue until both recurrences are automatic.