Senior LevelData Structures & Algorithms
How do you solve Matrix Chain Multiplication using Dynamic Programming?
ā Interview Prompt: Find the optimal parenthesisation of matrix chain multiplication minimising scalar multiplications using interval DP in O(NĀ³).
Problem:
Given matrices $A_1, A_2, ..., A_n$, find the order of multiplication that minimises the total number of scalar multiplications. Matrix multiplication is associative but not commutative.
Interval DP:
dp[i][j] = minimum cost to multiply matrices $A_i$ through $A_j$.
```
dp[i][j] = min over all k (i ā¤ k < j) of:
dp[i][k] + dp[k+1][j] + dims[i-1] dims[k] dims[j]
```
ā¢
Time: $O(N^3)$, Space: $O(N^2)$.
Code Implementation Example
typescript
// Matrix Chain Multiplication ā O(NĀ³)
function matrixChainOrder(dims: number[]): number {
const n = dims.length - 1; // number of matrices
const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
// l = chain length
for (let l = 2; l <= n; l++) {
for (let i = 0; i <= n - l; i++) {
const j = i + l - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const 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];
}
// dims = [10, 30, 5, 60] ā 3 matrices: 10Ć30, 30Ć5, 5Ć60
console.log(matrixChainOrder([10, 30, 5, 60])); // 4500š”Matrix Chain Multiplication O(NĀ³) interval DP minimising scalar operations.
šÆ Interview Key Takeaway
Matrix Chain is a classic interval DP. The recurrence splits chains at all possible midpoints k. Used in query plan optimisation, compiler expression evaluation.
#DSA#Matrix Chain#Interval DP#Dynamic Programming#Senior
Back to all Data Structures & Algorithms Questionsā