Matrix Chain Multiplication
The Matrix Chain Multiplication problem finds the most efficient way to multiply a chain of matrices. It's a DP problem that minimizes the number of scalar multiplications.
Given dimensions array dims where matrix i has dimensions dims[i-1] x dims[i], we need to parenthesize the product to minimize cost. Recurrence: dp[i][j] = min over k (dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j]).
Java implementation (bottom-up):
public static int matrixChainOrder(int[] dims) {
int n = dims.length - 1; // number of matrices
int[][] dp = new int[n][n];
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; 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] + dims[i]*dims[k+1]*dims[j+1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}
Two Minute Drill
- Matrix chain multiplication minimizes scalar multiplications.
- DP on intervals: O(n³) time, O(n²) space.
- State: dp[i][j] = min cost to multiply matrices i..j.
- Useful in compiler optimization and numerical linear algebra.
Need more clarification?
Drop us an email at career@quipoinfotech.com