Interval DP: Matrix Chain Multiplication, Optimal BST & Polygon Triangulation

1. Catalan Tree Spaces & The Interval Length Topological Order

How many ways can we parenthesize a product of $n$ matrices $A_1 A_2 \cdots A_n$, construct a Binary Search Tree on $n$ sorted keys, or triangulate a convex $(n+1)$-gon? The answer to all three is the $(n-1)$-th Catalan Number:

Because the last operation merges two contiguous sub-intervals $[i, k]$ and $[k+1, j]$ into $[i, j]$, any subproblem is uniquely identified by its pair of endpoints $(i, j)$ with $0 \le i \le j < n$—collapsing $\Theta(4^n / n^{3/2})$ trees into just $\binom{n+1}{2} = \Theta(n^2)$ distinct subproblems!

2. Three Isomorphic Interval DP Archetypes

• Matrix Chain Multiplication (Dimensions $p_0 \times p_1, p_1 \times p_2, \dots, p_{n-1} \times p_n$): Multiplying matrix $A_{i..k}$ ($p_i \times p_{k+1}$) by $A_{k+1..j}$ ($p_{k+1} \times p_{j+1}$) costs $p_i p_{k+1} p_{j+1}$ scalar multiplications: $$dp[i][j] = \min_{i \le k < j} \big(dp[i][k] + dp[k+1][j] + p_i \cdot p_{k+1} \cdot p_{j+1}\big)$$
• Minimum Weight Convex Polygon Triangulation (Vertices $0..n-1$): Every diagonal-free triangulation of sub-polygon $[i..j]$ includes exactly one triangle $(i, k, j)$ on base edge $(i, j)$ for some apex $i < k < j$: $$dp[i][j] = \min_{i < k < j} \big(dp[i][k] + dp[k][j] + \text{weight}(\triangle i k j)\big)$$
• Burst Balloons / Reverse Action Trick: If popping balloon $k$ first causes $k-1$ and $k+1$ to become adjacent, the left and right subproblems are not independent! Instead, guess which balloon $k \in (i, j)$ is popped LAST inside open interval $(i, j)$: its neighbors at the moment it pops are guaranteed to be the fixed boundary balloons $i$ and $j$, making $(i, k)$ and $(k, j)$ 100% independent!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <cstdint>
#include <limits>
#include <vector>

// 1. Matrix Chain Multiplication with Transpose-Cache Optimization (p has size n + 1)
long long matrix_chain_multiplication(const std::vector<long long>& p) {
    const int n = static_cast<int>(p.size()) - 1;
    if (n <= 1) return 0;
    constexpr long long INF = 1LL << 60;

    // dp[i][j] = min scalar multiplications for A_i .. A_j
    // dpT[j][i] = transposed copy of dp[i][j] so inner k-loop has stride-1 on both arrays!
    std::vector<std::vector<long long>> dp(n, std::vector<long long>(n, 0));
    std::vector<std::vector<long long>> dpT(n, std::vector<long long>(n, 0));

    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i + len - 1 < n; ++i) {
            const int j = i + len - 1;
            const long long outer_p = p[i] * p[j + 1];
            long long best = INF;
            for (int k = i; k < j; ++k) {
                // Both dp[i][k] and dpT[j][k + 1] are contiguous in memory along index k!
                long long cost = dp[i][k] + dpT[j][k + 1] + outer_p * p[k + 1];
                if (cost < best) best = cost;
            }
            dp[i][j] = best;
            dpT[j][i] = best;
        }
    }
    return dp[0][n - 1];
}

// 2. Burst Balloons: Guess the LAST balloon popped inside open interval (i, j)
long long max_coins_burst_balloons(const std::vector<int>& nums) {
    // Pad with virtual boundary balloons of value 1 at both ends
    std::vector<long long> a;
    a.reserve(nums.size() + 2);
    a.push_back(1);
    for (int x : nums) if (x > 0) a.push_back(x);
    a.push_back(1);

    const int m = static_cast<int>(a.size());
    std::vector<std::vector<long long>> dp(m, std::vector<long long>(m, 0));

    // len is the distance j - i between open interval boundaries (minimum 2)
    for (int len = 2; len < m; ++len) {
        for (int i = 0; i + len < m; ++i) {
            const int j = i + len;
            const long long boundary_prod = a[i] * a[j];
            long long best = 0;
            for (int k = i + 1; k < j; ++k) {
                best = std::max(best, dp[i][k] + dp[k][j] + boundary_prod * a[k]);
            }
            dp[i][j] = best;
        }
    }
    return dp[0][m - 1];
}