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.

Sources: Wikipedia: Matrix chain multiplication

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

function minMergeCost(sizes: number[]): number {
    const n = sizes.length;
    const prefix: number[] = [0];
    for (const s of sizes) prefix.push(prefix[prefix.length - 1] + s);
    const dp: number[][] = Array.from({ length: n }, () => new Array<number>(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];
}

def min_merge_cost(sizes):
    n = len(sizes)
    prefix = [0]
    for s in sizes:
        prefix.append(prefix[-1] + s)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = min(
                dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i])
                for k in range(i, j)
            )
    return dp[0][n - 1]

function minMergeCost(array $sizes): int {
    $n = count($sizes);
    $prefix = [0];
    foreach ($sizes as $s) $prefix[] = end($prefix) + $s;
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    for ($len = 2; $len <= $n; $len++) {
        for ($i = 0; $i + $len - 1 < $n; $i++) {
            $j = $i + $len - 1;
            $dp[$i][$j] = PHP_INT_MAX;
            for ($k = $i; $k < $j; $k++) {
                $cost = $dp[$i][$k] + $dp[$k + 1][$j] + ($prefix[$j + 1] - $prefix[$i]);
                $dp[$i][$j] = min($dp[$i][$j], $cost);
            }
        }
    }
    return $dp[0][$n - 1];
}

    public static int minMergeCost(int[] sizes) {
        int n = sizes.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + sizes[i];
        int[][] dp = new int[n][n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int 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];
    }

    public static int MinMergeCost(int[] sizes) {
        int n = sizes.Length;
        var prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + sizes[i];
        var dp = new int[n][];
        for (int i = 0; i < n; i++) dp[i] = new int[n];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = int.MaxValue;
                for (int k = i; k < j; k++) {
                    int 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?

Use DP on intervals when the problem statement says “combine adjacent pieces at some cost”, “best way to split a range into two parts” or “matrix chain multiplication order”. A solution built on it usually runs in O(n^3).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is DP on intervals confused with?

DP on intervals is most often confused with Dynamic programming (1-D), DP on subsequences (LIS / LCS / edit distance), DP on trees and Greedy (exchange argument).

• 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?

Interview problems solved with DP on intervals include Burst balloons, Longest palindromic subsequence, Minimum score triangulation, Strange printer, Remove boxes, Count palindromic substrings and Minimum cost to merge stones.

• 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?

The target complexity of DP on intervals is O(n3).

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