Interval Dynamic Programming

Interval DP solves subproblems on contiguous ranges. Matrix-chain multiplication is a clean example:matrix order is fixed, but parentheses can change the number of scalar multiplications dramatically. Each final multiplication splits an interval into two shorter intervals. We compute the cheapest cost and reconstruct a parenthesization, without multiplying any actual matrix entries.

Prerequisites: Two-Dimensional DP; recursion and matrix dimensions. Related existing lessons: Matrix Multiplication.

Build the idea

1. Recognize the repeated subproblems

   A chain of n matrices has Catalan-many parenthesizations. Different trees repeatedly solve the same subchain. Its optimal multiplication cost depends only on its endpoints because the dimensions of its resulting matrix are fixed by those endpoints. n≤200 permits O(n²) interval states with O(n) split candidates each.

2. Define the state

   Matrix Ai has dimensions d[i]×d[i+1] in zero-based storage. dp[l][r] is the minimum scalar-multiplication cost for Ai with l≤i≤r, in their original order. split[l][r] records the final split k. The product dimensions are d[l]×d[r+1], independent of how the interval is parenthesized, so endpoints are sufficient state.

3. Derive the transition

   Try every final split k from l to r−1. Compute left and right subchains optimally, then multiply their products:cost dp[l][k]+dp[k+1][r]+d[l]·d[k+1]·d[r+1]. The shared inner dimension is d[k+1]. Taking the minimum covers every binary parenthesization according to its final multiplication.

   $$\mathrm{dp}\left[l\right]\left[r\right]=\min \mathrm{over}k\mathrm{of}\mathrm{dp}\left[l\right]\left[k\right]+\mathrm{dp}[k+1]\left[r\right]+d\left[l\right]d[k+1]d[r+1]$$

4. Base cases and computation order

   A single matrix needs no multiplication, so dp[i][i]=0. Fill increasing interval length from 2 to n. Both subchains are strictly shorter and already computed. Initialize longer intervals to INF before minimizing. Reconstruct recursively using the stored split; one-matrix leaves print their 1-based names. The recursion is only for the final n-leaf expression.

5. Correctness and invariant

   Every legal parenthesization has a unique final split, whose children cannot be more expensive than optimal child values. Conversely combining two optimal children at a split constructs a legal solution. Induction on length therefore proves both the recurrence and the stored choice. This uses fixed matrix order; reordering matrices generally changes the mathematical product and is forbidden.

6. Work the example

   Dimensions [10,30,5,60] give three matrices. Multiplying A1A2 first costs 10·30·5=1500 and leaves a 10×5 matrix; the final multiplication costs 3000, for 4500. The other order costs 9000+18000=27000. Output ((A1*A2)*A3) witnesses the smaller cost.

   interval	minimum cost
   A1/A2/A3 separately	0
   A1..A2	1500
   A2..A3	9000
   A1..A3	4500

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
std::string order(int l,int r,const std::vector<std::vector<int>>&split){
    if(l==r){
        return "A"+std::to_string(l+1);
    }
    int k=split[l][r];
    return "("+order(l,k,split)+"*"+order(k+1,r,split)+")";
}
int main(){
    int n;
    std::cin>>n;
    std::vector<long long>d(n+1);
    for(auto&x:d){
        std::cin>>x;
    }
    const long long INF=4000000000000000000LL;
    std::vector<std::vector<long long>>dp(n,std::vector<long long>(n));
    std::vector<std::vector<int>>split(n,std::vector<int>(n));
    for(int length=2;length<=n;++length){
        for(int l=0;l+length<=n;++l){
            int r=l+length-1;
            dp[l][r]=INF;
            for(int k=l;k<r;++k){
                long long candidate=dp[l][k]+dp[k+1][r]+d[l]*d[k+1]*d[r+1];
                if(candidate<dp[l][r]){
                    dp[l][r]=candidate;
                    split[l][r]=k;
                }
            }
        } // Shorter intervals precede longer intervals.
    }
    std::cout<<dp[0][n-1]<<'\n'<<order(0,n-1,split)<<'\n';
}

Complexity analysis

O(n²) interval states and O(n) splits each:O(n³) time, O(n²) values/splits. The expression has O(n) tokens; the simple recursive string concatenation can take O(n² log(n+1)) additional character-copy work and O(n) stack, dominated by the DP. Costs≤(n−1)·10^9 fit long long.

Example input and output

Read n (1..200), then n+1 compatible chain dimensions in 1..1000. Print minimum scalar-multiplication count and one parenthesization using A1…An.

Input

3
10 30 5 60

Output

4500
((A1*A2)*A3)

Dimensions [10,30,5,60] give three matrices. Multiplying A1A2 first costs 10·30·5=1500 and leaves a 10×5 matrix; the final multiplication costs 3000, for 4500. The other order costs 9000+18000=27000. Output ((A1*A2)*A3) witnesses the smaller cost.

Practical applications

Use when a final split separates a contiguous range into independent subranges:parsing, ordered merges and chain products. Partition DP usually fixes a number of prefix groups and has a previous-layer transition instead of two same-layer child intervals.

Check your understanding

Why fill interval lengths increasingly?

Put it into practice

Enumerate all parenthesizations for four matrices and compare costs.