Interval DP: Matrix Chain, OBST & Palindrome Cuts

1. Problem and Motivation

Interval DP is the family of dynamic programming problems where the state is a range [i, j] of the input — a subarray of numbers, a substring, a subsequence of matrices, a contiguous run of keys — rather than a single prefix or a single index. The recurrence almost always asks the same question: "what is the last operation performed on this range, or where does this range split?" It then tries every candidate split point k inside [i, j], combines the optimal answers for the two resulting sub-ranges [i, k] and [k+1, j], and keeps the best combination.

That single idea — range as state, try every split point — is why interval DP problems share a recognizable shape even though they solve very different problems: minimizing scalar multiplications in a matrix product, minimizing expected search cost in a binary search tree, minimizing cuts to make every piece a palindrome, or minimizing the cost to merge a row of piles into one.

                Why $O(n^3)$ shows up so often: there are $O(n^2)$ distinct ranges [i, j] in an input of size $n$ (choose any start and any end), and for each range the recurrence tries up to $O(n)$ split points. $O(n^2)$ ranges times $O(n)$ split points per range gives $O(n^3)$ total work — the signature complexity of interval DP, before any further optimization.
            

2. Prerequisites

This lesson builds directly on two earlier parts of the series and does not repeat either:

Dynamic Programming Foundations (Part 14) — the six-step method for designing any DP solution (state, recurrence, base case, order of evaluation, space, reconstruction). Interval DP is just one particular choice of "what the state means"; if the general DP design steps are unfamiliar, start there first.
FAANG Interview Pattern Recognition — Interval DP: Burst Balloons — that lesson already derives the full recurrence, proof sketch, and three-language implementation for Burst Balloons (LeetCode 312), the canonical "last operation in a range" interval DP problem. This lesson does not repeat Burst Balloons. It does, however, lean on the exact same mental model established there — a range [i, j] and a split point k — and applies it to four problems that lesson did not cover.

3. A Concrete Example

Worked Example

Matrix Chain Multiplication by hand: four matrices

Suppose we must multiply four matrices $A_1 A_2 A_3 A_4$ with dimensions $40\times20$, $20\times30$, $30\times10$, and $10\times30$. Multiplying two matrices of size $p\times q$ and $q\times r$ costs $p\cdot q\cdot r$ scalar multiplications, and matrix multiplication is associative, so the order of parenthesization changes the total cost without changing the result. Represent the chain as dimension array p = [40, 20, 30, 10, 30], where matrix $A_i$ has shape $p_{i-1}\times p_i$ (1-indexed). Let dp[i][j] be the minimum cost to multiply $A_i \cdots A_j$. The table must be filled by increasing interval length, because dp[i][j] depends on shorter sub-ranges nested inside it.

Length	Range [i,j]	Best split k	Computation	dp[i][j]
1	[1,1] [2,2] [3,3] [4,4]	—	single matrix, no multiplication	0
2	[1,2]	k=1	$40\times20\times30$	24000
2	[2,3]	k=2	$20\times30\times10$	6000
2	[3,4]	k=3	$30\times10\times30$	9000
3	[1,3]	k=1	dp[1][1]+dp[2][3]+$40\times20\times10$ = 0+6000+8000	14000
3	[2,4]	k=3	dp[2][3]+dp[4][4]+$20\times10\times30$ = 6000+0+6000	12000
4	[1,4]	k=3	dp[1][3]+dp[4][4]+$40\times10\times30$ = 14000+0+12000	26000

At length 4 the recurrence also checked k=1 (cost 36000) and k=2 (cost 69000) before settling on k=3 as the cheapest split. Following the winning splits back — [1,4] splits at k=3, and [1,3] splits at k=1 — reconstructs the optimal parenthesization $((A_1(A_2A_3))A_4)$.

4. Matrix Chain Multiplication

                Core insight: dp[i][j] = the minimum number of scalar multiplications needed to fully parenthesize and compute the product $A_i A_{i+1} \cdots A_j$. The recurrence tries every split point k in [i, j-1] — the last multiplication performed is $(A_i\cdots A_k)\times(A_{k+1}\cdots A_j)$ — and adds the cost of that final multiply: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j], where p[i-1]*p[k]*p[j] is the cost of multiplying the two resulting matrices of shape $p_{i-1}\times p_k$ and $p_k\times p_j$.
            

The cost table alone tells you how much work the optimal order takes, not what that order is. To recover the actual parenthesization, keep a second table split[i][j] recording which k achieved the minimum for each range, then walk it recursively: the left half is however split[i][k] parenthesizes [i, k], and the right half is however split[k+1][j] parenthesizes [k+1, j].

def matrix_chain_order(p):
    """p has n+1 dims for n matrices; matrix i (1-indexed) has shape p[i-1] x p[i]."""
    n = len(p) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    split = [[0] * (n + 1) for _ in range(n + 1)]

    for length in range(2, n + 1):
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    split[i][j] = k
    return dp, split


def build_parenthesization(split, i, j):
    if i == j:
        return f"A{i}"
    k = split[i][j]
    left = build_parenthesization(split, i, k)
    right = build_parenthesization(split, k + 1, j)
    return f"({left}{right})"


p = [40, 20, 30, 10, 30]
dp, split = matrix_chain_order(p)
n = len(p) - 1
print("Minimum multiplications:", dp[1][n])                       # 26000
print("Optimal parenthesization:", build_parenthesization(split, 1, n))  # ((A1(A2A3))A4)

// Matrix Chain Multiplication: minimum cost + reconstructed parenthesization
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

pair<vector<vector<long long>>, vector<vector<int>>> matrixChainOrder(const vector<int>& p) {
    int n = p.size() - 1;
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    vector<vector<int>> split(n + 1, vector<int>(n + 1, 0));

    for (int length = 2; length <= n; length++) {
        for (int i = 1; i <= n - length + 1; i++) {
            int j = i + length - 1;
            dp[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++) {
                long long cost = dp[i][k] + dp[k + 1][j] + (long long)p[i - 1] * p[k] * p[j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    split[i][j] = k;
                }
            }
        }
    }
    return {dp, split};
}

string buildParenthesization(const vector<vector<int>>& split, int i, int j) {
    if (i == j) return "A" + to_string(i);
    int k = split[i][j];
    return "(" + buildParenthesization(split, i, k) + buildParenthesization(split, k + 1, j) + ")";
}

int main() {
    vector<int> p = {40, 20, 30, 10, 30};
    auto result = matrixChainOrder(p);
    auto dp = result.first;
    auto split = result.second;
    int n = p.size() - 1;
    cout << "Minimum multiplications: " << dp[1][n] << endl;                         // 26000
    cout << "Optimal parenthesization: " << buildParenthesization(split, 1, n) << endl; // ((A1(A2A3))A4)
}

// Matrix Chain Multiplication: minimum cost + reconstructed parenthesization
public class MatrixChainOrder {
    static long[][] dp;
    static int[][] split;

    static void computeOrder(int[] p) {
        int n = p.length - 1;
        dp = new long[n + 1][n + 1];
        split = new int[n + 1][n + 1];

        for (int length = 2; length <= n; length++) {
            for (int i = 1; i <= n - length + 1; i++) {
                int j = i + length - 1;
                dp[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    long cost = dp[i][k] + dp[k + 1][j] + (long) p[i - 1] * p[k] * p[j];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        }
    }

    static String buildParenthesization(int i, int j) {
        if (i == j) return "A" + i;
        int k = split[i][j];
        return "(" + buildParenthesization(i, k) + buildParenthesization(k + 1, j) + ")";
    }

    public static void main(String[] args) {
        int[] p = {40, 20, 30, 10, 30};
        computeOrder(p);
        int n = p.length - 1;
        System.out.println("Minimum multiplications: " + dp[1][n]);                         // 26000
        System.out.println("Optimal parenthesization: " + buildParenthesization(1, n));       // ((A1(A2A3))A4)
    }
}

5. Optimal Binary Search Tree

This section assumes basic BST vocabulary — nodes, depth, search cost — from BST & Balanced Trees (Part 10) and does not re-derive it. The new idea here is entirely about the DP, not about how BSTs work.

                Core insight: given sorted keys $k_i, \ldots, k_j$ with known access frequencies, dp[i][j] = the minimum total expected search cost of a BST built from exactly those keys. Try every key r in [i, j] as the root: everything in [i, r-1] becomes the left subtree, everything in [r+1, j] becomes the right subtree, and dp[i][j] = min over r of dp[i][r-1] + dp[r+1][j] + freqSum(i, j). The freqSum(i, j) term is added once per range rather than recomputed per key, because choosing any root for range [i, j] pushes every key already inside [i, r-1] and [r+1, j] one level deeper than it was inside its own subtree — one extra comparison for every one of those keys, which is exactly freqSum(i, j).
            

def optimal_bst(keys, freq):
    n = len(keys)
    prefix = [0] * (n + 1)          # prefix[i] = sum of freq[0..i-1]
    for i in range(n):
        prefix[i + 1] = prefix[i] + freq[i]

    dp = [[0] * n for _ in range(n)]
    root = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = freq[i]
        root[i][i] = i

    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            freq_sum = prefix[j + 1] - prefix[i]
            for r in range(i, j + 1):
                left = dp[i][r - 1] if r > i else 0
                right = dp[r + 1][j] if r < j else 0
                cost = left + right + freq_sum
                if cost < dp[i][j]:
                    dp[i][j] = cost
                    root[i][j] = r
    return dp[0][n - 1], root


keys = [10, 12, 20]
freq = [34, 8, 50]
cost, root = optimal_bst(keys, freq)
print("Minimum search cost:", cost)                 # 142
print("Root key:", keys[root[0][len(keys) - 1]])    # 20

// Optimal Binary Search Tree
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

pair<vector<vector<long long>>, vector<vector<int>>> optimalBST(const vector<int>& freq) {
    int n = freq.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + freq[i];

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    vector<vector<int>> root(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) { dp[i][i] = freq[i]; root[i][i] = i; }

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            dp[i][j] = LLONG_MAX;
            long long freqSum = prefix[j + 1] - prefix[i];
            for (int r = i; r <= j; r++) {
                long long left = (r > i) ? dp[i][r - 1] : 0;
                long long right = (r < j) ? dp[r + 1][j] : 0;
                long long cost = left + right + freqSum;
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    root[i][j] = r;
                }
            }
        }
    }
    return {dp, root};
}

int main() {
    vector<int> keys = {10, 12, 20};
    vector<int> freq = {34, 8, 50};
    auto result = optimalBST(freq);
    auto dp = result.first;
    auto root = result.second;
    int n = freq.size();
    cout << "Minimum search cost: " << dp[0][n - 1] << endl;          // 142
    cout << "Root key: " << keys[root[0][n - 1]] << endl;              // 20
}

// Optimal Binary Search Tree
public class OptimalBST {
    public static void main(String[] args) {
        int[] keys = {10, 12, 20};
        int[] freq = {34, 8, 50};
        int n = freq.length;

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + freq[i];

        long[][] dp = new long[n][n];
        int[][] root = new int[n][n];

        for (int i = 0; i < n; i++) { dp[i][i] = freq[i]; root[i][i] = i; }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Long.MAX_VALUE;
                long freqSum = prefix[j + 1] - prefix[i];
                for (int r = i; r <= j; r++) {
                    long left = (r > i) ? dp[i][r - 1] : 0;
                    long right = (r < j) ? dp[r + 1][j] : 0;
                    long cost = left + right + freqSum;
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        root[i][j] = r;
                    }
                }
            }
        }

        System.out.println("Minimum search cost: " + dp[0][n - 1]);        // 142
        System.out.println("Root key: " + keys[root[0][n - 1]]);            // 20
    }
}

6. Palindrome Partitioning (Minimum Cuts)

                Core insight: dp[i] = the minimum number of cuts needed to partition the prefix s[0..i] (inclusive) so every piece is a palindrome. For each candidate last piece s[j..i], if that piece is itself a palindrome then dp[i] = min(dp[i], dp[j-1] + 1). Checking "is s[j..i] a palindrome" naively costs $O(n)$ per check, which would make the whole algorithm $O(n^3)$. Precomputing an isPalindrome[i][j] table first — itself a smaller interval DP, filled by increasing length exactly like the tables above — turns every palindrome check into $O(1)$ after $O(n^2)$ preprocessing, so the combined algorithm is $O(n^2)$.
            

The precomputation recurrence is: a single character is always a palindrome; a two-character range is a palindrome exactly when its endpoints match; and for longer ranges, isPalindrome[i][j] = (s[i] == s[j]) and isPalindrome[i+1][j-1] — the outer characters must match and the strictly smaller inner range must already be known to be a palindrome, which is why the table is filled by increasing interval length.

def min_cut(s):
    n = len(s)
    if n == 0:
        return 0

    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                is_pal[i][j] = (length == 2) or is_pal[i + 1][j - 1]

    cuts = [0] * n
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0                       # whole prefix is already one palindrome
        else:
            cuts[i] = i                       # worst case: cut before every character
            for j in range(1, i + 1):
                if is_pal[j][i] and cuts[j - 1] + 1 < cuts[i]:
                    cuts[i] = cuts[j - 1] + 1
    return cuts[n - 1]


print(min_cut("aab"))    # 1  -> "aa" | "b"
print(min_cut("aabbc"))  # 2  -> "aa" | "bb" | "c"

// Palindrome Partitioning: minimum cuts (LeetCode 132)
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int minCut(const string& s) {
    int n = s.size();
    if (n == 0) return 0;

    vector<vector<bool>> isPal(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) isPal[i][i] = true;

    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            if (s[i] == s[j]) {
                isPal[i][j] = (length == 2) || isPal[i + 1][j - 1];
            }
        }
    }

    vector<int> cuts(n, 0);
    for (int i = 0; i < n; i++) {
        if (isPal[0][i]) {
            cuts[i] = 0;
        } else {
            cuts[i] = i;
            for (int j = 1; j <= i; j++) {
                if (isPal[j][i] && cuts[j - 1] + 1 < cuts[i]) {
                    cuts[i] = cuts[j - 1] + 1;
                }
            }
        }
    }
    return cuts[n - 1];
}

int main() {
    cout << minCut("aab") << endl;    // 1
    cout << minCut("aabbc") << endl;  // 2
}

// Palindrome Partitioning: minimum cuts (LeetCode 132)
public class PalindromePartitioning {
    static int minCut(String s) {
        int n = s.length();
        if (n == 0) return 0;

        boolean[][] isPal = new boolean[n][n];
        for (int i = 0; i < n; i++) isPal[i][i] = true;

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    isPal[i][j] = (length == 2) || isPal[i + 1][j - 1];
                }
            }
        }

        int[] cuts = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPal[0][i]) {
                cuts[i] = 0;
            } else {
                cuts[i] = i;
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i] && cuts[j - 1] + 1 < cuts[i]) {
                        cuts[i] = cuts[j - 1] + 1;
                    }
                }
            }
        }
        return cuts[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minCut("aab"));    // 1
        System.out.println(minCut("aabbc"));  // 2
    }
}

7. Interval Merge DP

Matrix Chain Multiplication and Burst Balloons look unrelated on the surface — one multiplies matrices, the other pops balloons — but both fit the same template.

The General Merge Pattern

Given a sequence of items, repeatedly merge two adjacent groups into one, paying some cost each time, until only one group remains; minimize (or maximize) the total cost. The state is again a range [i, j], and the recurrence tries every split point k: dp[i][j] = best over k of dp[i][k] + dp[k+1][j] + combine(i, k, j), where combine(i, k, j) is whatever it costs to merge the two already-solved sub-ranges into one. Matrix Chain Multiplication's combine is p[i-1]*p[k]*p[j] (the cost of one matrix multiply); Burst Balloons' combine is nums[i-1]*nums[k]*nums[j] (the coins from the last balloon burst — see Burst Balloons). A third natural choice for combine is a plain sum: merging two adjacent piles of stones costs the total weight of the two piles being combined.

Example

Minimum cost to merge piles into one

Piles [4, 3, 3, 4]: merging (4,3) first and (3,4) first each cost 7, then merging the two resulting piles [7, 7] costs 14 more, for a total of 28 — cheaper than merging left-to-right, which costs 7 + 10 + 14 = 31.

def min_merge_cost(piles):
    n = len(piles)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + piles[i]

    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(0, n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            pile_sum = prefix[j + 1] - prefix[i]   # combine(i, k, j) for every k
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + pile_sum
                if cost < dp[i][j]:
                    dp[i][j] = cost
    return dp[0][n - 1]


print(min_merge_cost([4, 3, 3, 4]))  # 28

// Minimum cost to merge adjacent piles into one (unrestricted pairwise merge)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

long long minMergeCost(const vector<int>& piles) {
    int n = piles.size();
    vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + piles[i];

    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int length = 2; length <= n; length++) {
        for (int i = 0; i <= n - length; i++) {
            int j = i + length - 1;
            dp[i][j] = LLONG_MAX;
            long long pileSum = prefix[j + 1] - prefix[i];
            for (int k = i; k < j; k++) {
                long long cost = dp[i][k] + dp[k + 1][j] + pileSum;
                if (cost < dp[i][j]) dp[i][j] = cost;
            }
        }
    }
    return dp[0][n - 1];
}

int main() {
    vector<int> piles = {4, 3, 3, 4};
    cout << minMergeCost(piles) << endl;  // 28
}

// Minimum cost to merge adjacent piles into one (unrestricted pairwise merge)
public class StoneMerge {
    static long minMergeCost(int[] piles) {
        int n = piles.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + piles[i];

        long[][] dp = new long[n][n];
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                dp[i][j] = Long.MAX_VALUE;
                long pileSum = prefix[j + 1] - prefix[i];
                for (int k = i; k < j; k++) {
                    long cost = dp[i][k] + dp[k + 1][j] + pileSum;
                    if (cost < dp[i][j]) dp[i][j] = cost;
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] piles = {4, 3, 3, 4};
        System.out.println(minMergeCost(piles));  // 28
    }
}

8. Complexity Comparison Table

Problem	State Definition	Time	Space
Matrix Chain Multiplication	`dp[i][j]` = min cost to multiply matrices `i..j`	$O(n^3)$	$O(n^2)$
Optimal Binary Search Tree	`dp[i][j]` = min expected search cost of a BST over keys `i..j`	$O(n^3)$	$O(n^2)$
Palindrome Partitioning	`dp[i]` = min cuts for prefix `0..i`, backed by an $O(n^2)$ `isPalindrome[i][j]` table	$O(n^2)$	$O(n^2)$
Interval Merge (Stone Merging)	`dp[i][j]` = min cost to merge piles `i..j` into one	$O(n^3)$	$O(n^2)$

Every row shares the same $O(n^2)$-ranges times $O(n)$-split-points shape from Section 1, except Palindrome Partitioning: its outer loop over prefixes and inner loop over candidate last pieces is only $O(n^2)$ combined, with the $O(n^2)$ palindrome precomputation adding no extra asymptotic cost.

9. Applications and Alternatives

Where interval DP shows up in real systems

Compilers: optimizing the evaluation order of a chain of associative operations — such as reordering a sequence of matrix or tensor multiplications in a numerical library — is a direct application of Matrix Chain Multiplication's cost model.
Databases: query optimizers choosing the join order for a multi-table query use a cost-based interval DP: the "range" is a subset of tables to join, and the optimizer tries every split point to decide which sub-joins to compute first, minimizing estimated I/O or row-comparison cost.
Compiler symbol tables and static dictionaries: when lookup frequencies are known in advance and the structure is built once and queried many times, Optimal BST minimizes total expected comparisons — the same idea behind Huffman-adjacent static lookup structures.

All of these are alternatives to a greedy or fixed-order approach: evaluating a matrix chain left-to-right, joining tables in listed order, or building a plain balanced BST that ignores frequency are all simpler but strictly no better than the interval-DP optimum, and can be considerably worse when the input is skewed.

10. Exercises and Mastery

Easy

Run Matrix Chain Multiplication on the dimension array p = [10, 20, 30, 40, 30] (four matrices). Fill the dp table by hand, by increasing interval length, and report the minimum multiplication count.

Medium

Using the Palindrome Partitioning code above, compute the minimum number of cuts for "abccbc". Build the isPalindrome table first, then trace the cuts array index by index.

Hard

Design (code optional) a generalization of the stone-merging problem from Section 7 where you may merge any K adjacent piles at once instead of exactly 2, paying the sum of those K piles each time, and you must end with exactly one pile. What changes about the state, and why does the split step now need to consider groupings of K rather than a single split point k? For the original two-way version of the pattern, revisit Burst Balloons, where the "last operation in the range" is a balloon burst rather than a merge.

Mastery challenge: A database query planner must choose the join order for eight tables with known selectivity estimates. Model it as an interval DP: define the state, the recurrence over split points, the combine cost, and the final complexity. Then explain what changes if two different join algorithms (say, hash join vs. nested loop) are both available at every split — does the state need to grow?

Review rhythm: tomorrow, re-derive the Matrix Chain Multiplication recurrence and reconstruct a parenthesization without notes; next week, implement Optimal BST and Palindrome Partitioning from the core insight alone; several weeks later, work through the Hard exercise's K-way merge design and check whether the "range + split point" idea still applies once the split becomes a partition into K groups instead of two.

11. Summary Cheat Sheet

Interval DP state is a range [i, j]; the recurrence tries every split point k and combines the two resulting sub-ranges.
$O(n^2)$ ranges times $O(n)$ split points per range gives the signature $O(n^3)$ time and $O(n^2)$ space.
Matrix Chain Multiplication: dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]; reconstruct the parenthesization with a secondary split table.
Optimal BST: dp[i][j] = min over r of dp[i][r-1] + dp[r+1][j] + freqSum(i,j); the frequency sum is added once per range because every key in the two subtrees gets one level deeper.
Palindrome Partitioning: precompute isPalindrome[i][j] as its own interval DP, then run a cheap $O(n^2)$ cut-counting DP on top of it.
Interval Merge DP generalizes both Matrix Chain Multiplication and Burst Balloons: only the combine(i,k,j) cost function changes — a product for matrices and balloons, a sum for stone piles.
Burst Balloons itself is already covered in FAANG Interview Pattern Recognition — this lesson deliberately did not repeat it.

Cookie Consent

Interval DP: Matrix Chain, Optimal BST & Palindrome Cuts

Table of Contents

1. Problem and Motivation

2. Prerequisites

3. A Concrete Example

Matrix Chain Multiplication by hand: four matrices

4. Matrix Chain Multiplication

5. Optimal Binary Search Tree

6. Palindrome Partitioning (Minimum Cuts)

7. Interval Merge DP

The General Merge Pattern

Minimum cost to merge piles into one

8. Complexity Comparison Table

9. Applications and Alternatives

Where interval DP shows up in real systems

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Interval DP: Matrix Chain, Optimal BST & Palindrome Cuts

Table of Contents

1. Problem and Motivation

2. Prerequisites

3. A Concrete Example

Matrix Chain Multiplication by hand: four matrices

4. Matrix Chain Multiplication

5. Optimal Binary Search Tree

6. Palindrome Partitioning (Minimum Cuts)

7. Interval Merge DP

The General Merge Pattern

Minimum cost to merge piles into one

8. Complexity Comparison Table

9. Applications and Alternatives

Where interval DP shows up in real systems

10. Exercises and Mastery

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

FAANG Interview Pattern Recognition

BST & Balanced Trees (Part 10)