Interval DP

State = a range [i, j]; solve smaller ranges first, combine by trying every split point k inside the range. Recognize this pattern by the phrasing: "given a sequence, find the optimal way to combine/remove/partition it."

Sub-patterns

• A — Matrix-Chain Style. Optimal order to combine a chain of operations.
• B — Partitioning DP. Optimal way to split a sequence into pieces.
• C — Remove-and-Combine DP. Optimal order to remove or merge elements of a sequence.

Practice set (5)

• Medium — Palindrome Partitioning II
• Hard — Minimum Cost to Cut a Stick, Burst Balloons, Strange Printer, Remove Boxes