MatrixChainMultiplication.java

packagecom.thealgorithms.dynamicprogramming;

importjava.util.ArrayList;
importjava.util.Arrays;

/**
 * The MatrixChainMultiplication class provides functionality to compute the
 * optimal way to multiply a sequence of matrices. The optimal multiplication
 * order is determined using dynamic programming, which minimizes the total
 * number of scalar multiplications required.
 */
publicfinalclassMatrixChainMultiplication {
privateMatrixChainMultiplication() {
 }

// Matrices to store minimum multiplication costs and split points
privatestaticint[][] m;
privatestaticint[][] s;
privatestaticint[] p;

/**
 * Calculates the optimal order for multiplying a given list of matrices.
 *
 * @param matrices an ArrayList of Matrix objects representing the matrices
 * to be multiplied.
 * @return a Result object containing the matrices of minimum costs and
 * optimal splits.
 */
publicstaticResultcalculateMatrixChainOrder(ArrayList<Matrix> matrices) {
intsize = matrices.size();
m = newint[size + 1][size + 1];
s = newint[size + 1][size + 1];
p = newint[size + 1];

for (inti = 0; i < size + 1; i++) {
Arrays.fill(m[i], -1);
Arrays.fill(s[i], -1);
 }

for (inti = 0; i < p.length; i++) {
p[i] = i == 0 ? matrices.get(i).col() : matrices.get(i - 1).row();
 }

matrixChainOrder(size);
returnnewResult(m, s);
 }

/**
 * A helper method that computes the minimum cost of multiplying
 * the matrices using dynamic programming.
 *
 * @param size the number of matrices in the multiplication sequence.
 */
privatestaticvoidmatrixChainOrder(intsize) {
for (inti = 1; i < size + 1; i++) {
m[i][i] = 0;
 }

for (intl = 2; l < size + 1; l++) {
for (inti = 1; i < size - l + 2; i++) {
intj = i + l - 1;
m[i][j] = Integer.MAX_VALUE;

for (intk = i; k < j; k++) {
intq = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (q < m[i][j]) {
m[i][j] = q;
s[i][j] = k;
 }
 }
 }
 }
 }

/**
 * The Result class holds the results of the matrix chain multiplication
 * calculation, including the matrix of minimum costs and split points.
 */
publicstaticclassResult {
privatefinalint[][] m;
privatefinalint[][] s;

/**
 * Constructs a Result object with the specified matrices of minimum
 * costs and split points.
 *
 * @param m the matrix of minimum multiplication costs.
 * @param s the matrix of optimal split points.
 */
publicResult(int[][] m, int[][] s) {
this.m = m;
this.s = s;
 }

/**
 * Returns the matrix of minimum multiplication costs.
 *
 * @return the matrix of minimum multiplication costs.
 */
publicint[][] getM() {
returnm;
 }

/**
 * Returns the matrix of optimal split points.
 *
 * @return the matrix of optimal split points.
 */
publicint[][] getS() {
returns;
 }
 }

/**
 * The Matrix class represents a matrix with its dimensions and count.
 */
publicstaticclassMatrix {
privatefinalintcount;
privatefinalintcol;
privatefinalintrow;

/**
 * Constructs a Matrix object with the specified count, number of columns,
 * and number of rows.
 *
 * @param count the identifier for the matrix.
 * @param col the number of columns in the matrix.
 * @param row the number of rows in the matrix.
 */
publicMatrix(intcount, intcol, introw) {
this.count = count;
this.col = col;
this.row = row;
 }

/**
 * Returns the identifier of the matrix.
 *
 * @return the identifier of the matrix.
 */
publicintcount() {
returncount;
 }

/**
 * Returns the number of columns in the matrix.
 *
 * @return the number of columns in the matrix.
 */
publicintcol() {
returncol;
 }

/**
 * Returns the number of rows in the matrix.
 *
 * @return the number of rows in the matrix.
 */
publicintrow() {
returnrow;
 }
 }
}