Interval DP
You've seen range-based DP. Here you solve Matrix Chain Multiplication and Burst Balloons, where you split intervals and combine subproblem answers.
Lessons
1. What Interval DP Solves
Merge, split, combine
2. When to Use Interval DP
When subproblems nest inside
3. Problem - Zuma
CF 607B - remove palindromes
4. Zuma - Why Naive Fails
Same endpoints merge free
5. Zuma - Defining the DP
dp[l][r] = moves to clear
6. Zuma - Transition
Match ends, split, or single
7. Zuma - Base Cases
Empty = 0, single = 1
8. Zuma - Implementation
Bottom-up by length
9. Zuma - Time and Space
O(n³) with O(n²) states
10. Problem - Merge Stones
LC 1000 - merge k at a time
11. Merge Stones - Feasibility Check
When is one pile possible?
12. Merge Stones - Defining the DP
Piles mod (k-1) matters
13. Merge Stones - Core Logic
Step by k-1 in splits
14. Merge Stones - Implementation
Prefix sums for merge cost
15. Problem - Coloring Brackets
CF 149D - color matched brackets
16. Coloring Brackets - Why Naive Fails
Matching structure guides DP
17. Coloring Brackets - Defining the DP
4D state: positions and colors
18. Coloring Brackets - Core Logic
Inside first, then combine
19. Coloring Brackets - Implementation
Stack finds the pairs
20. Problem - Polygon Triangulation
LC 1039 - triangulate polygon
21. Polygon Triangulation - Why Naive Fails
One triangle per edge
22. Polygon Triangulation - Defining the DP
dp[l][r] for vertex range
23. Polygon Triangulation - Core Logic
Try each apex vertex k
24. Polygon Triangulation - Implementation
O(n³) for n vertices
25. Problem - Minimum Cost to Cut Stick
LC 1547 - cutting costs
26. Minimum Cost to Cut Stick - Solution
Add 0 and n as boundaries
27. Problem - Strange Printer
LC 664 - overwriting printer
28. Strange Printer - Solution
Extend matching chars free
29. Problem - Remove Boxes
LC 546 - group same colors
30. Remove Boxes - Solution
3D: track trailing boxes
31. Quiz: Interval DP Patterns
What makes interval DP?
32. Quiz: Interval DP Edge Cases
Empty ranges, single elements
33. Common Mistakes in Interval DP
Length order, not index order
34. Problem - Encode String with Shortest Length
LC 471
35. Encode String with Shortest Length - Implementation
Solution approach
36. Problem - Palindrome Removal
LC 1246
37. Palindrome Removal - Implementation
Solution approach
38. Section Recap
From MCM to Remove Boxes