Interval DP

You’ll recognise it when

• The input is a sequence (a string, a row of balloons, a stick with marks) and the question is about a contiguous range of it, usually the whole thing.
• Solving a range means deciding something about its two ends (do they pair up?) or about where to split it (which multiplication happens last, which cut goes first).
• After that decision, what’s left is again one or two contiguous ranges, just shorter.
• n is in the hundreds or low thousands, because the table has about n² cells.

It’s easy to confuse with an ordinary prefix DP like knapsack, where dp[i] covers the first i items. A prefix only ever grows at one end. Reach for interval DP when both ends move, or when two pieces from the middle get combined.

The idea

To check that “level” is a palindrome, you compare the outer letters, l and l, then look at what’s between them, “eve”, and repeat. Each step works on a shorter piece of the same word, marked by where it starts and where it ends.

Interval DP turns that into a table. dp[i][j] holds the answer for the piece from position i to position j, and each piece’s answer uses only shorter pieces inside it. So fill the table in order of length: all pieces of length 1, then length 2, and so on. By the time you reach a piece, everything it needs is already there.

This page works through one problem: the longest palindromic subsequence. A subsequence keeps some letters in their order and skips the rest, so “debugged” contains “degged”, a palindrome of length 6. Look at the end letters of a piece. If they’re equal, they can be the outer pair around the best palindrome inside. If they differ, they can’t both be used, so drop one of them and keep whichever side does better.

How it works

dp[i][j] is the length of the longest palindromic subsequence of s[i..j], so only cells with i ≤ j matter: the upper triangle. The graphic fills it one diagonal at a time as you scroll, on “debugged”.

Why it’s correct: take any palindromic subsequence of s[i..j]. If it doesn’t use s[i], it fits inside s[i+1..j], so it’s no longer than dp[i+1][j]. If it doesn’t use s[j], likewise for dp[i][j-1]. If it uses both, they’re its outer letters, so they’re equal and the rest is a palindrome inside s[i+1..j-1]. The recurrence covers all three cases, and each case reads a shorter piece that an earlier diagonal already filled.

def longest_palindrome_subseq(s):
    """Length of the longest subsequence of s that reads the same both ways."""
    n = len(s)
    if n == 0:
        return 0
    # dp[i][j] = answer for the substring s[i..j]; cells with i > j mean
    # "nothing in between" and stay 0.
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):                          # short intervals first
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

// Length of the longest subsequence of s that reads the same both ways.
int longestPalindromeSubseq(const string& s) {
    int n = s.size();
    if (n == 0) return 0;
    // dp[i][j] = answer for the substring s[i..j]; cells with i > j mean
    // "nothing in between" and stay 0.
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int length = 2; length <= n; length++) {               // short intervals first
        for (int i = 0; i + length - 1 < n; i++) {
            int j = i + length - 1;
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

class Palindrome {
    // Length of the longest subsequence of s that reads the same both ways.
    static int longestPalindromeSubseq(String s) {
        int n = s.length();
        if (n == 0) return 0;
        // dp[i][j] = answer for the substring s[i..j]; cells with i > j mean
        // "nothing in between" and stay 0.
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {                  // short intervals first
            for (int i = 0; i + length - 1 < n; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(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];
    }
}

Why loop by length? A cell reads the cell below it, so filling row 0 first would read row 1 before it exists. Any order that finishes shorter pieces first works. Looping by length is the one that’s obviously right for every interval problem. For this recurrence, running i from n - 1 down to 0 with j going up also works, and it’s what you’ll often see:

for i in range(n - 1, -1, -1):
    dp[i][i] = 1
    for j in range(i + 1, n):
        ...   # same two cases

The other flavour: choosing a split point

In the palindrome problem, a piece only looks at its two ends. The other big family decides where to split the piece: every k between i and j is a candidate, and the answer is the best one.

dp[i][j] = min over k of  dp[i][k] + dp[k+1][j] + cost(i, k, j)

The classic example is matrix chain multiplication. Multiplying a 10×30 matrix by a 30×5 one costs 10·30·5 multiplications, and in a chain, the order you group them in changes the total a lot. Whatever the grouping, some multiplication happens last, joining the product of matrices i..k to the product of k+1..j. Try every k:

# matrix m has dims[m] rows and dims[m + 1] columns
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] + dims[i] * dims[k + 1] * dims[j + 1]
                       for k in range(i, j))

Same table, same length order, one more loop. Burst balloons and cutting a stick have this shape too; see Variations.

Why it’s O(n²)

There are n(n + 1) / 2 cells with i ≤ j, and each is filled with one comparison and a max, so the time is O(n²) and the table is O(n²) memory. With n = 1500 that’s about 1.1 million cells.

The split-point flavour does up to j - i work per cell, which adds up to about n³ / 6 steps: O(n³) time, still O(n²) memory, since k is looped over and never stored. That’s why those problems usually have n in the hundreds.

For the palindrome problem, row i only reads row i + 1, so with i going down you can keep two rows and use O(n) memory.

Common mistakes

for i in range(n):                    # ✗ reads row i + 1 before it's filled
for i in range(n - 1, -1, -1):        # ✓ row i + 1 is already done

dp[i][j] = dp[i + 1][j - 1]                     # ✗ gives 1 for "aab"
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])      # ✓ gives 2

dp[i][k] + dp[k][j]          # ✗ for matrices i..j: matrix k is in both halves
dp[i][k] + dp[k + 1][j]      # ✓ halves i..k and k+1..j

Variations

• Burst balloons. Bursting a balloon earns the product of it and its current neighbours. Pad the row with a 1 at each end, and let dp[l][r] be the best total for the balloons strictly between l and r. The trick is to choose k as the balloon burst last in that gap: its neighbours are then exactly l and r, and the two sides never interact. dp[l][r] = max(dp[l][k] + a[l]·a[k]·a[r] + dp[k][r]).
• Minimum cost to cut a stick. Each cut costs the length of the piece being cut. Sort the cut positions and add 0 and the stick length as sentinels, c. Then dp[i][j] = c[j] - c[i] + min(dp[i][k] + dp[k][j]) over cuts k strictly between i and j, where k is the first cut made in that piece. Indexing by cuts, not by coordinates, keeps the table small when the stick is long.
• Matrix chain multiplication and polygon triangulation. The split-point recurrence above. Triangulating a convex polygon is the same shape: the edge from vertex i to vertex j belongs to exactly one triangle i, k, j, which splits the rest into two smaller polygons.
• Palindrome partitioning. To cut a string into the fewest palindromes, first fill pal[i][j] with the substring recurrence from the mistakes above, by length. Then run a 1-D DP over prefixes: the best split of s[0..j] is 1 + the best split of s[0..i-1], minimised over every i with pal[i][j] true. The number of cuts is the number of pieces minus 1. O(n²) in total.
• Top-down instead of by length. A memoised recursion solve(i, j) computes pieces in whatever order it needs them, so you don’t have to think about the fill order at all. The cost is recursion depth up to n and slower constant factors; the bottom-up loop by length avoids both.