Java matrix-chain DP: minimize multiplication work without reordering matrices

This complete program targets Java 8. Its displayed output is checked by the tutorial validation script.

Order is fixed, grouping is not

The dimension sequence ten, twenty, thirty, forty describes three compatible matrices. Multiplying the first two before the third costs 18000 scalar multiplications; the other grouping costs 32000. The recurrence considers every split of an interval instead of applying a local cheapest-pair rule.

An interval containing one matrix costs zero because no multiplication is required. Larger intervals combine the two smaller interval costs with the product of their outer and split dimensions. The program returns the cost, not the parenthesized expression or the numeric matrix result.

Bound arithmetic before allocating state

The fixture accepts at most ten matrices and dimensions between one and one thousand. Multiplication is promoted to long before the product is formed. Those declared bounds keep every candidate cost within long; unrestricted dimensions would need checked arithmetic or a wider representation.

The algorithm assumes ordinary dense matrix multiplication as its cost model. Cache behavior, sparsity and different multiplication algorithms can change real runtime. Benchmark boundaries prevent an operation-count model from being mistaken for a measured performance ranking.

Working program

public class MatrixPlanCost {
    static long minimum(int[] dimensions) {
        if(dimensions.length<2 || dimensions.length>11)throw new IllegalArgumentException("chain size");
        for(int dimension:dimensions)if(dimension<1 || dimension>1000)throw new IllegalArgumentException("dimension");
        int count=dimensions.length-1;long[][] cost=new long[count][count];
        for(int length=2;length<=count;length++)for(int left=0;left+length<=count;left++) {
            int right=left+length-1;cost[left][right]=Long.MAX_VALUE;
            for(int split=left;split<right;split++) {
                long candidate=cost[left][split]+cost[split+1][right]
                    +(long)dimensions[left]*dimensions[split+1]*dimensions[right+1];
                cost[left][right]=Math.min(cost[left][right],candidate);
            }
        }
        return cost[0][count-1];
    }
    public static void main(String[] args) {
        System.out.println(minimum(new int[]{10,20,30,40}));System.out.println(minimum(new int[]{10,20}));
        try{minimum(new int[]{10,0,20});}catch(IllegalArgumentException rejected){System.out.println("dimension rejected");}
    }
}

Output

18000
0
dimension rejected

Costs and boundaries

For n matrices the recurrence takes O(n cubed) time and O(n squared) storage. Returning the actual grouping needs split storage and reconstruction. This fixture caps n at ten and does not allocate or multiply the matrices themselves.

Common Mistakes

• Preserve matrix order while changing parentheses.
• Promote before multiplying dimensions.
• Do not interpret a scalar-count estimate as a runtime benchmark.

Read next

Java bottom-up tabulation: dependency order and unreachable states, Java 0/1 knapsack: reverse capacity iteration prevents reuse, Java JMH benchmarks: consumed results, fixtures and limited measurements.