DP on intervals

O(n^3)

dp[i][j] holds the cheapest cost to fully combine the span [i..j]. Fill by growing span length, trying every split point k inside the span so both halves are already solved.

Signals

combine adjacent pieces at some costbest way to split a range into two partsmatrix chain multiplication ordermerge cost depends on the whole spanoptimal parenthesization or build order

Template

function minMergeCost(sizes) {
    const n = sizes.length;
    const prefix = [0];
    for (const s of sizes) prefix.push(prefix[prefix.length - 1] + s);
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i + len - 1 < n; i++) {
            const j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i; k < j; k++) {
                const cost = dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i]);
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

Looks similar, isn't

Dynamic programming (1-D): Plain 1-D dp[i] only looks back at the previous one or two indices. Interval DP fills dp[i][j] for every span and tries every SPLIT point k inside it, because the cost of combining [i..j] depends on where you cut it, not on a fixed previous index.

n up to ~300..500 segments, trying every split point for every span -> O(n^3): O(n^2) spans times O(n) split choices each.

Learn this pattern