Interval DP

The state is a contiguous range dp[l][r], and the transition splits it at some point $k$. $O(n^2)$ states, $O(n)$ transitions, so $O(n^3)$ — feasible for $n\le 400$-$500$.

The skeleton

for (int len = 2; len <= n; len++)              // by increasing length
    for (int l = 0; l + len <= n; l++) {
        int r = l + len;
        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));
    }

Iterating by length is the whole trick. Both sub-intervals are strictly shorter than the current one, so they are already computed. Looping l then r directly gives wrong answers.

The two shapes

Split at a point

dp[l][r] = min over k of dp[l][k] + dp[k][r] + cost — matrix chain, merging stones, optimal BST, polygon triangulation.

Peel from an end

dp[l][r] from dp[l+1][r] and dp[l][r-1] — palindromes, two-player games on an array, removing boxes.

// longest palindromic subsequence
for (int l = n - 1; l >= 0; l--) {
    dp[l][l] = 1;
    for (int r = l + 1; r < n; r++)
        dp[l][r] = (s[l] == s[r]) ? dp[l+1][r-1] + 2
                                  : max(dp[l+1][r], dp[l][r-1]);
}

Note the reversed outer loop: dp[l][*] depends on dp[l+1][*], so $l$ must decrease.

The classics

Problem	Recurrence
Matrix chain multiplication	split, cost $p_l{p}_k{p}_r$
Merging stones / burning piles	split, cost = sum of the range
Optimal binary search tree	split, cost = sum of frequencies in the range
Longest palindromic subsequence	peel both ends
Minimum insertions to make a palindrome	$n-\mathrm{LPS}$
Polygon triangulation	split at a triangle apex
Burst balloons	split on the last balloon burst — the trick is choosing the last, not the first
Removing boxes	needs a third dimension: dp[l][r][k] for $k$ extra boxes attached
Zuma / stone game	dp[l][r] with a game-theoretic max/min
Optimal strategy for a game	dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1])

Burst balloons — the “last, not first” idea

Choosing which balloon to burst first leaves two ranges whose costs interact. Choosing which to burst last means everything else in the range is already gone, so the two sides are independent:

$dp[l][r]={\max }_{l<k<r}(dp[l][k]+dp[k][r]+a_l\cdot a_k\cdot a_r).$

When an interval DP seems not to decompose, ask whether reversing the decision order fixes it.

Making it $O(n^2)$

Condition	Technique
Cost satisfies the quadrangle inequality	Knuth optimization — restrict $k$ to $[\mathrm{opt}[l][r-1],\mathrm{opt}[l+1][r]]$
Alphabetic tree with fixed leaf order	Hu-Tucker / Garsia-Wachs, $O(n\log n)$
Totally monotone cost matrix	SMAWK

Verify the quadrangle inequality on small random inputs before relying on it — see Yao’s theorem for the exact conditions.

Game variants

Two players alternate taking from the ends of an array. Define dp[l][r] as the current player’s advantage (their score minus the opponent’s) on that range:

$dp[l][r]=\max (a_l-dp[l+1][r],a_r-dp[l][r-1]).$

The subtraction encodes the role swap. This one line handles a large family of “optimal play on an array” problems — see Game DP.

Circular intervals

For problems on a circle (necklaces, circular merging), duplicate the array to length $2n$ and take the best window of length $n$:

for (int i = 0; i < n; i++) ans = min(ans, dp[i][i + n]);

$O(n^3)$ becomes $O(8n^3)$ — check the limits before committing.

See also: Matrix Chain · Knuth Optimization · Game DP