DP on intervals

How does DP on intervals work?

The state is a pair, the two ends of a range. It holds the best result inside those bounds.

Loop over the length of the range, from short to long. Every range you read is already finished.

For one range, try every split point inside it. Each split gives one candidate answer.

A candidate combines the left part, the right part and the cost of joining them. Keep the best of them.

The joining cost is where the problem actually lives. In burst balloons it depends on the two boundaries.

The answer is the state covering the whole input. It is the very last range filled.

1. padded: [1, 3, 1, 5, 1]Bursting balloons. A one is added at each end and never bursts.
2. width one ranges: 0There is nothing inside them to burst.
3. dp(1, 3) = 15Bursting the 1 between 3 and 5 pays 3 times 1 times 5.
4. dp(0, 3) = 30Burst the 3 last, so it is worth 1 times 3 times 5.
5. dp(0, 4) = 35The 5 goes last. Every shorter range was already done.

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];
}

A worked example of DP on intervals

Longest palindromic subsequence

Return the length of the longest palindromic subsequence in a string.

The letters do not have to sit next to each other.

The state is a range of the string.

If the two ends match, they add two to the range inside. If not, drop one end and take the better side.

function longestPalindromeSubseq(s) {
    const n = s.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));

    // i walks backwards so every inner range is already filled
    for (let i = n - 1; i >= 0; i--) {
        dp[i][i] = 1; // a single letter is a palindrome

        for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[0][n - 1];
}

When should you use DP on intervals?

These phrases in a problem statement point here:

• •combine adjacent pieces at some cost
• •best way to split a range into two parts
• •matrix chain multiplication order
• •merge cost depends on the whole span
• •optimal parenthesization or build order

What is DP on intervals confused with?

• Dynamic programming (1-D): One index describes a prefix. A range needs both of its ends.
• DP on subsequences (LIS / LCS / edit distance): There the two indices point into two different sequences. Here both sit in one.
• DP on trees: A tree splits at its children, which are given. An interval splits at a point you choose.
• Greedy (exchange argument): Greedy would pick an order and commit to it. Here every split point has to be tried.

Common mistakes with DP on intervals

• Looping i and j like a normal grid

  A range must be filled after everything inside it. Loop by length, or walk i backwards.

• Choosing the first move instead of the last

  In burst balloons only the last burst has fixed neighbours. Picking the first makes the state wrong.

• Forgetting the padding

  A neutral value at each end removes the edge cases. Without it the boundaries need special code.

• Running it on a large input

  O(n cubed) dies past a few thousand items. Check n before writing three loops.

Which interview problems use DP on intervals?

• Burst balloons: Choose which balloon is burst last.
• Longest palindromic subsequence: The two ends match, or one is dropped.
• Minimum score triangulation: Every split point forms a triangle.
• Strange printer: One print covers a whole range.
• Remove boxes: The state carries an extra count alongside the range.
• Count palindromic substrings: Count every range that is a palindrome.
• Minimum cost to merge stones: Split into groups of k rather than two.

What is the time and space complexity of DP on intervals?

O(n^3)

n up to about 500 gives O(n cubed). There are n squared ranges, each with n split points.