Week 14 — Advanced DP
Month 03, Week 2. The hardest DP patterns interviewers throw at Senior+ candidates.
Theme
Five DP variants that share a common challenge: the recurrence is non-obvious and the order of subproblem decomposition matters. Specifically:
- Interval DP (p71 Burst Balloons): split by last action, not first.
- State-machine DP over two pointers (p72 Regex Match): the
*operator’s “match 0 or many” forces branching. - 2D grid DP from string interleaving (p73): proving non-greedy via counterexample.
- Subsequence counting DP (p74 Distinct Subsequences): include/exclude on every match.
- Partition DP with palindrome preprocessing (p75): O(n²) palindrome table + O(n²) cut DP.
Daily Schedule
| Day | Problem | LC | Pattern |
|---|---|---|---|
| Mon | p71 Burst Balloons | 312 | Interval DP, split by LAST balloon |
| Tue | p72 Regular Expression Matching | 10 | 2D DP, * matches 0 or many |
| Wed | p73 Interleaving String | 97 | 2D DP, why greedy fails |
| Thu | p74 Distinct Subsequences | 115 | 2D DP, include/exclude on match |
| Fri | p75 Palindrome Partitioning II | 132 | 2-phase DP, min cuts |
Readiness Gate
You can leave this week when you can:
- Explain why interval DP for Burst Balloons splits on the LAST balloon (not first).
- Write the regex DP recurrence cold, articulating the
*case in plain English. - Give a concrete counterexample for why greedy interleaving check fails.
- State the include/exclude split for Distinct Subsequences.
- Compute the O(n²) palindrome table separately from the O(n²) cut DP.
Mental Model: “Subproblem Decomposition Choice”
For DP problems beyond the textbook, the key insight is what to enumerate at each step. Burst Balloons fails if you split on “first balloon to burst”; it works splitting on “last balloon remaining in interval (i,j).” This decomposition-direction sensitivity is the hallmark of Hard DP.