Proficient.
Put your skills to the test.

Problem summary

Find the minimum number of scalar multiplications needed to multiply a chain of matrices with dimensions R[i−1] by R[i]. Parentheses may change, but matrix order is fixed.

Constraints

2 ≤ n ≤ 100; 1 ≤ R[i] ≤ 1000.

Worked example

An independently prepared example for this explanation.

4
10 20 50 1 100

2200

Solution analysis

1. Let dp[l][r] be the minimum multiplication cost for matrices l through r. A single matrix costs zero. If the last multiplication splits after k, its two operands have dimensions R[l] by R[k+1] and R[k+1] by R[r+1] in zero-based matrix indexing.
2. Try every split k: dp[l][k] + dp[k+1][r] + R[l]*R[k+1]*R[r+1]. Fill intervals in increasing length so both shorter subchains are already solved.
3. For dimensions 10,20,50,1,100, first multiply the 20×50 and 50×1 matrices at cost 1000. Multiplying by the initial 10×20 matrix costs 200, then multiplying by the last 1×100 matrix costs 1000. The total is 2200.

Why it works

Every parenthesization has a final multiplication dividing the chain into two consecutive subchains. Its cost is exactly one recurrence candidate. Replacing either subchain by a cheaper parenthesization cannot affect its dimensions and improves the whole result. Induction on interval length therefore establishes that the recurrence attains precisely the optimum.

Watch out. Do not reorder matrices, use the correct three dimension indices, and store costs in 64-bit integers: up to 99 products of size 10^9 can be necessary.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<limits>
#include<algorithm>
// Algorithm: Let dp[l][r] be the minimum multiplication cost for matrices l through r.
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<long long>dimension(n+1);
    for(auto&value:dimension){
        cin>>value;
    }
    vector<vector<long long>>cost(n,vector<long long>(n,0));
    for(int length=2;length<=n;++length){
        for(int left=0;left+length<=n;++left){
            int right=left+length-1;
            cost[left][right]=numeric_limits<long long>::max();
            for(int split=left;split<right;++split){
                long long candidate=cost[left][split]+cost[split+1][right];
                candidate+=dimension[left]*dimension[split+1]*dimension[right+1];
                cost[left][right]=min(cost[left][right],candidate);
            }
        }
    }
    cout<<cost[0][n-1]<<'\n';
}