v. Interval DP

State = a contiguous range $[l, r)$ . Transitions either split at some $k$ (dp[l][k] and dp[k][r]), or peel an end (dp[l+1][r], dp[l][r-1]). $O (n^{2})$ states × $O (n)$ splits = $O (n^{3})$ , fine for $n \leq 400$ – $500$ . Iterate by increasing length (or $l$ decreasing, $r$ increasing) so both halves are ready.

for (int len = 2; len <= n; len++)
    for (int l = 0, r = len; r <= n; l++, r++) {
        dp[l][r] = INF;
        for (int k = l + 1; k < r; k++) dp[l][r] = min(dp[l][r], dp[l][k] + dp[k][r] + cost(l, k, r));
    }

Catalogue

Problem	Recurrence
matrix chain ( $p_{0} .. p_{n}$ )	$d p_{l, r} = min_{k} d p_{l, k} + d p_{k, r} + p_{l} p_{k} p_{r}$
merging adjacent piles (cost = merged size)	split, cost $= sum (l, r)$ ; Knuth makes it $O (n^{2})$ ; Garsia–Wachs $O (n lo g n)$
optimal BST with access frequencies	split at the root, cost $= sum of frequencies$ ; Knuth $O (n^{2})$ (Knuth)
convex polygon triangulation	split at the apex of the triangle on edge $(l, r)$ ; cost is the triangle’s weight (area, perimeter, whatever the problem charges)
burst balloons	choose the balloon burst last: $d p_{l, r} = max_{k} d p_{l, k} + d p_{k, r} + a_{l} a_{k} a_{r}$ (exclusive bounds)
longest palindromic subsequence	peel: $s_{l} = s_{r}$ ? $d p_{l + 1, r - 1} + 2$ : $max (d p_{l + 1, r}, d p_{l, r - 1})$
minimum insertions to make a palindrome	$n - LPS$
take from either end, two players, maximise difference	$d p_{l, r} = max (a_{l} - d p_{l + 1, r}, a_{r} - d p_{l, r - 1})$
strange printer (min strokes to paint a string)	merge with an equal character, below
removing boxes ( $score = k^{2}$ per block)	add a dimension: extra equal boxes attached on the right
longest regular bracket subsequence / colouring brackets	split at the partner of $s_{l}$
context-free grammar membership (CYK)	split, over nonterminals
circular arrays	double the array, answer $min_{i} d p_{i, i + n}$ (cost becomes $O (8 n^{3})$ from $O (n^{3})$ — check the limits before committing)
zero-out a range with “decrement a subarray” moves	$\sum max (0, a_{i} - a_{i - 1})$ , no DP needed

Choosing the last operation

When the first decision makes the two sides interact (bursting a balloon makes its neighbours adjacent), decide the last event instead: everything else in the range has already happened, and the boundaries $l, r$ are still present, so the two sides are independent.

Proof: burst balloons recurrence

Pad $a$ with $a_{0} = a_{n + 1} = 1$ and let $d p_{l, r}$ be the best score for bursting all balloons strictly between $l$ and $r$ while $l$ and $r$ are still present. Fix the last balloon $k$ burst in $(l, r)$ . Before it, balloons in $(l, k)$ and $(k, r)$ are burst while $k$ is present, so balloons on one side never have a neighbour on the other side: the two sides are independent subproblems with boundaries $(l, k)$ and $(k, r)$ , scoring $d p_{l, k}$ and $d p_{k, r}$ at best. When $k$ is burst, its neighbours are exactly $l$ and $r$ : score $a_{l} a_{k} a_{r}$ . Every order decomposes this way for its last balloon, and every pair of sub-orders combines into a valid order, so the maximum over $k$ is the optimum.

Games on an array

$d p_{l, r}$ = (score of the player to move) − (score of the other) on the remaining range. Taking $a_{l}$ leaves the opponent to move on $[l + 1, r]$ with advantage $d p_{l + 1, r}$ from their point of view:

$d p_{l, r} = max (a_{l} - d p_{l + 1, r}, a_{r} - d p_{l, r - 1}) .$

With an even number of elements, the first player can always guarantee at least half (take all odd or all even positions), but the DP gives the exact value. See Game DP for the general theory this is a special case of.

Proof: the negamax recurrence

The game on $[l, r]$ is zero-sum in the difference of scores. If the mover takes $a_{l}$ , their final difference is $a_{l}$ minus the difference the opponent achieves on $[l + 1, r]$ playing optimally as the mover there, which is $d p_{l + 1, r}$ by induction on length. The mover chooses the better of the two moves. “Odd or even positions” works because after the first player takes an end with the chosen parity, both ends available to the second player have the other parity, so the first player can always take the chosen parity again.

Strange printer

Minimum strokes to print $s$ , where a stroke paints a contiguous segment with one colour over whatever is there:

$d p_{i, j} = min (d p_{i, j - 1} + 1, min_{i \leq k < j, s_{k} = s_{j}} d p_{i, k} + d p_{k + 1, j - 1}), d p_{i, i - 1} = 0.$

int strangePrinter(const string& s) {
    int n = sz(s); vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));   // dp[i][j+1] for s[i..j]
    for (int i = n - 1; i >= 0; i--) for (int j = i; j < n; j++) {
        int& d = dp[i][j + 1]; d = dp[i][j] + 1;
        for (int k = i; k < j; k++) if (s[k] == s[j]) d = min(d, dp[i][k + 1] + dp[k + 1][j]);
    }
    return n ? dp[0][n] : 0;
}

Proof sketch: the printer recurrence

Strokes can be assumed nested or disjoint (laminar), because if two strokes partially overlap, the earlier one can be shortened to the part not covered by the later one. Consider the stroke that gives $s_{j}$ its final colour. If it covers no other final-colour position in $[i, j]$ , it can be shrunk to ${j}$ , costing $d p_{i, j - 1} + 1$ . Otherwise let $k < j$ be the rightmost other position it finally colours; then $s_{k} = s_{j}$ and the stroke spans $[k, j]$ , with everything in $(k, j)$ painted by later strokes nested inside it ( $d p_{k + 1, j - 1}$ ), and the stroke can be charged to the solution for $[i, k]$ (extend the stroke that colours $s_{k}$ to also cover $j$ ). Conversely both expressions describe valid printing plans.

Removing boxes

dp[l][r][k] = best score for boxes $l .. r$ when $k$ boxes equal to box $r$ are glued after $r$ :

$d p_{l, r, k} = max ((k + 1)^{2} + d p_{l, r - 1, 0}, max_{l \leq m < r, c_{m} = c_{r}} d p_{l, m, k + 1} + d p_{m + 1, r - 1, 0}) .$

$O (n^{4})$ , fast in practice. The “glued extra items” dimension is the general fix when merging blocks of equal elements is beneficial (Zuma-like problems).

Brackets and grammars

Longest regular bracket subsequence: $d p_{l, r} = max (d p_{l + 1, r}, max_{k : s_{l}, s_{k} match} 2 + d p_{l + 1, k - 1} + d p_{k + 1, r})$ .
Counting colourings of a given regular sequence (each pair: one bracket coloured, adjacent coloured brackets differ): DP over the matching tree, $d p [l] [r] [left colour] [right colour]$ .
CYK (grammar in Chomsky normal form): can[l][r][A] iff $A \Rightarrow^{*} s [l, r)$ ; combine can[l][m][B] and can[m][r][C] for each rule $A \to B C$ . $O (n^{3} \cdot ∣ R ∣)$ ; with bitsets over nonterminals, faster. Counting parse trees is the same loops with sums and products. A general grammar must be converted to CNF first (eliminate $ε$ and unit rules, binarise any right-hand side longer than 2) before CYK applies.

// rules: term[A] = set of chars, bin = {A, B, C} for A -> B C
bool cyk(const string& s, int K, int start, const vector<vector<char>>& term, const vector<array<int, 3>>& bin) {
    int n = sz(s); if (!n) return false;
    vector<vector<vector<char>>> can(n, vector<vector<char>>(n + 1, vector<char>(K)));
    for (int i = 0; i < n; i++) for (int A = 0; A < K; A++) can[i][i + 1][A] = term[A][(unsigned char)s[i]];
    for (int len = 2; len <= n; len++) for (int l = 0; l + len <= n; l++) for (int m = l + 1; m < l + len; m++)
        for (auto [A, B, C] : bin) if (can[l][m][B] && can[m][l + len][C]) can[l][l + len][A] = 1;
    return can[0][n][start];
}

Speedups

Condition	Technique	Result
cost satisfies the quadrangle inequality and is monotone on inclusion	Knuth: $opt_{l, r - 1} \leq opt_{l, r} \leq opt_{l + 1, r}$	$O (n^{2})$
merging piles in fixed order (alphabetic trees)	Garsia–Wachs / Hu–Tucker	$O (n lo g n)$
only $O (n)$ “interesting” intervals (e.g. split by the maximum)	DP on the Cartesian tree	$O (n)$ – $O (n lo g n)$
matrix chain	Hu–Shing (convex polygon partitioning)	$O (n lo g n)$ , rarely needed

Matrix chain does not satisfy the quadrangle inequality in general, so Knuth’s optimisation is invalid there; it is valid for optimal BST and pile merging. This is a common mix-up — Knuth’s own $O (n^{2})$ result was specifically for optimal BSTs, whose cost (sum of frequencies) is Monge, not for matrix chain’s $p_{l} p_{k} p_{r}$ , which isn’t.

When merge order can be chosen freely (the leaves may be permuted, e.g. picking which items to merge first with no fixed left-to-right sequence), plain greedy Huffman coding solves the $n lo g n$ version directly; when the order is fixed (as in matrix chain, optimal BST, polygon triangulation), you need Hu–Tucker/Garsia–Wachs or a Knuth-optimised $O (n^{2})$ DP instead — matrix chain is the hard case precisely because its order is fixed and its cost isn’t Monge.

Polygon triangulation and matrix chain are the same recurrence, and the correspondence is a genuine bijection: each parenthesisation of the matrix product corresponds to a triangulation of a convex $(n + 1)$ -gon, which is why the number of parenthesisations (equivalently, triangulations) is the Catalan number $C_{n - 1}$ (Catalan Numbers).

Interval DP in the wild: optimising a chain of matrix multiplications, database join-order optimisation (same shape as matrix chain), tensor-contraction ordering in ML frameworks.

whoashish's cp notes

Directory