Java - Brackets in Matrix Chain Multiplication

Problem Statement

Given an array arr[] of size n representing the dimensions of matrices (matrix i has dimensions arr[i-1] x arr[i]), find:

The minimum number of scalar multiplications needed to multiply the chain.

The parenthesization that achieves this minimum.

Example

Input: arr = {40, 20, 30, 10, 30}

Output:

Minimum multiplications: 26000

Optimal Parenthesization: ((A1 x A2) x (A3 x A4))

import java.util.*;

public class MatrixChainMultiplication {

    // Function to compute matrix chain order and build brackets

    public static void matrixChainOrder(int[] arr) {

        int n = arr.length;

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

        int[][] bracket = new int[n][n];

        for (int len = 2; len < n; len++) {

            for (int i = 1; i < n - len + 1; i++) {

                int j = i + len - 1;

                dp[i][j] = Integer.MAX_VALUE;

                for (int k = i; k < j; k++) {

                    int cost = dp[i][k] + dp[k+1][j] + arr[i-1] * arr[k] * arr[j];

                    if (cost < dp[i][j]) {

                        dp[i][j] = cost;

                        bracket[i][j] = k;

                    }

                }

            }

        }

        System.out.println("Minimum multiplications: " + dp[1][n - 1]);

        System.out.println("Optimal Parenthesization: " + getOptimalParens(bracket, 1, n - 1, new int[]{1}));

    }

    // Function to construct the parenthesized output

    public static String getOptimalParens(int[][] bracket, int i, int j, int[] name) {

        if (i == j) {

            return "A" + (name[0]++);

        }

        int k = bracket[i][j];

        String left = getOptimalParens(bracket, i, k, name);

        String right = getOptimalParens(bracket, k + 1, j, name);

        return "(" + left + " x " + right + ")";

    }

    public static void main(String[] args) {

        int[] arr = {40, 20, 30, 10, 30};

        matrixChainOrder(arr);

    }

}