Matrix Chain Multiplication
In the context of dynamic programming, the Matrix Chain Multiplication problem involves finding the most efficient way to multiply a sequence of matrices.
Given a chain of matrices, where the i-th matrix has dimensions d[i-1] x d[i], the goal is to determine the minimum number of multiplications required to calculate the product of the entire chain.
To solve this problem, we can use a dynamic programming approach. We can define a 2D array dp of size (n x n), where n is the number of matrices in the chain.
The value of dp[i][j] represents the minimum number of multiplications required to calculate the product of matrices from the i-th matrix to the j-th matrix.
We can use the following recursive formula to fill the dp array:
TEXT/X-JAVA
1if (i == j) {
2 dp[i][j] = 0;
3} else {
4 dp[i][j] = Integer.MAX_VALUE;
5
6 for (int k = i; k < j; k++) {
7 int cost = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j];
8
9 if (cost < dp[i][j]) {
10 dp[i][j] = cost;
11 }
12 }
13}xxxxxxxxxx31
}import java.util.Arrays;public class MatrixChainMultiplication { public static int matrixChainMultiplication(int[] dimensions) { int n = dimensions.length; int[][] dp = new int[n][n]; for (int d = 1; d < n - 1; d++) { for (int i = 1; i < n - d; i++) { int j = i + d; dp[i][j] = Integer.MAX_VALUE; for (int k = i; k < j; k++) { int cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j]; if (cost < dp[i][j]) { dp[i][j] = cost; } } } } return dp[1][n - 1]; } public static void main(String[] args) { int[] dimensions = {10, 5, 20, 2, 12}; int minCost = matrixChainMultiplication(dimensions); System.out.println("Minimum cost for matrix chain multiplication: " + minCost);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
