This Java program solves the Matrix Chain Multiplication problem using dynamic programming. The goal is to find the optimal way to multiply a chain of matrices such that the number of scalar multiplications is minimized.
Java Program
public class MatrixChainMultiplication {
// Function to find the optimal way to multiply a chain of matrices
public static int matrixChainOrder(int[] dimensions) {
int n = dimensions.length;
// DP table to store the minimum number of multiplications
int[][] dp = new int[n][n];
// Initialize the diagonal of dp table to 0 (cost of multiplying one matrix is zero)
for (int i = 1; i < n; i++) {
dp[i][i] = 0;
}
// Length of the chain (start from 2 as length 1 is trivial)
for (int length = 2; length < n; length++) {
for (int i = 1; i < n – length + 1; i++) {
int j = i + length – 1;
dp[i][j] = Integer.MAX_VALUE;
// Try placing the split at every possible position and take the minimum
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k + 1][j] + dimensions[i – 1] * dimensions[k] * dimensions[j];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
// Return the minimum number of multiplications needed for the whole chain
return dp[1][n – 1];
}
public static void main(String[] args) {
// Example: dimensions of matrices in the chain
// A1 = 10×30, A2 = 30×5, A3 = 5×60, A4 = 60×10
int[] dimensions = {10, 30, 5, 60, 10};
// Calculate the minimum number of multiplications
int result = matrixChainOrder(dimensions);
System.out.println(“Minimum number of multiplications is: ” + result);
}
}
Explanation of the Program Structure
This program solves the Matrix Chain Multiplication problem using dynamic programming. The goal is to minimize the number of scalar multiplications required to multiply a chain of matrices.
- matrixChainOrder function: This function computes the minimum number of scalar multiplications required to multiply a chain of matrices. It takes an array
dimensions[]as input, where the length of the array isn, and the matrix dimensions areAi = dimensions[i-1] x dimensions[i]. - Dynamic Programming Table (dp): The DP table
dp[i][j]is a 2D array where each entry represents the minimum number of scalar multiplications required to multiply matrices fromAitoAj. The algorithm fills this table by exploring all possible ways to split the matrices into two smaller chains and choosing the split with the fewest multiplications. - Main logic: The program iterates through increasing lengths of matrix chains and calculates the minimum cost of multiplying them. The table is filled using the relation:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + dimensions[i-1]*dimensions[k]*dimensions[j]) - Base case: When multiplying a single matrix (i.e., when the chain length is 1), no multiplications are needed. Therefore, the diagonal entries of the DP table are initialized to 0.
- main function: This function initializes a sample set of matrix dimensions and calls the
matrixChainOrderfunction to compute the minimum number of scalar multiplications needed. The result is then printed to the console.
Step-by-Step Process:
- We initialize a 2D dynamic programming table
dpof size(n x n), wherenis the number of matrices plus one (since the input is the dimensions array). - We start by filling the diagonal of the table with 0 because no multiplications are required for a single matrix.
- We then iterate through increasing lengths of matrix chains, trying every possible way to split the chain, and calculating the cost of multiplication for each split.
- The final result, stored in
dp[1][n-1], represents the minimum number of scalar multiplications needed to multiply the entire chain of matrices.
Example:
Consider the following dimensions of matrices in a chain:
A1 = 10x30, A2 = 30x5, A3 = 5x60, A4 = 60x10
The corresponding dimensions array is {10, 30, 5, 60, 10}.
The program will calculate that the minimum number of scalar multiplications required to multiply these matrices is:
Minimum number of multiplications is: 4500
Conclusion:
This Java program provides an efficient solution to the Matrix Chain Multiplication problem using dynamic programming. The time complexity of this solution is O(n^3), where n is the number of matrices. This approach ensures that the optimal solution is found by exploring all possible ways to split the matrix chain.
