Practice › Dynamic Programming
Matrix Chain Multiplication
Hard · Dynamic Programming · Asked at Amazon, Microsoft, Google, Flipkart
Matrix i has dimensions d[i-1] × d[i]. Find the minimum number of scalar multiplications needed to multiply the whole chain.
Input
First line: k (number of dimensions). Second line: k integers d[0..k−1] (so there are k − 1 matrices).
Output
The minimum cost.
Constraints
- 2 ≤ k ≤ 100
- 1 ≤ d[i] ≤ 500
Interval DP: cost[i][j] = min over split m of cost[i][m] + cost[m+1][j] + d[i−1]·d[m]·d[j].
Example 1
Input
5 40 20 30 10 30
Output
26000
Example 2
Input
3 10 20 30
Output
6000
Hints
- The last multiplication splits the chain i..j into (i..m) × (m+1..j) for some m.
- cost[i][j] = min over m of cost[i][m] + cost[m+1][j] + d[i−1]·d[m]·d[j]. Fill by increasing chain length.
Approach
Interval DP over matrices 1..k−1. cost[i][i] = 0. For chain lengths 2, 3, … and each start i, with j = i + len − 1, try every split m in [i, j): multiplying the two partial results costs d[i−1] × d[m] × d[j]. Filling by length guarantees the shorter sub-chains are already done. Costs reach about 100 × 500³ ≈ 1.25 × 10^10, so use 64 bits.
Complexity: O(k³) time · O(k²) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
cin >> k;
vector<long long> d(k);
for (auto &x : d) cin >> x;
int n = k - 1; // matrices 1..n, matrix i is d[i-1] x d[i]
vector<vector<long long>> cost(n + 1, vector<long long>(n + 1, 0));
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
cost[i][j] = LLONG_MAX;
for (int m = i; m < j; m++)
cost[i][j] = min(cost[i][j], cost[i][m] + cost[m + 1][j] + d[i - 1] * d[m] * d[j]);
}
cout << cost[1][n] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
k = data[0]
d = data[1 : k + 1]
n = k - 1 # matrices 1..n, matrix i is d[i-1] x d[i]
cost = [[0] * (n + 1) for _ in range(n + 1)]
for length in range(2, n + 1):
for i in range(1, n - length + 2):
j = i + length - 1
cost[i][j] = min(cost[i][m] + cost[m + 1][j] + d[i - 1] * d[m] * d[j] for m in range(i, j))
print(cost[1][n])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
long[] d = new long[k];
for (int i = 0; i < k; i++) d[i] = sc.nextLong();
int n = k - 1; // matrices 1..n, matrix i is d[i-1] x d[i]
long[][] cost = new long[n + 1][n + 1];
for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
cost[i][j] = Long.MAX_VALUE;
for (int m = i; m < j; m++)
cost[i][j] = Math.min(cost[i][j], cost[i][m] + cost[m + 1][j] + d[i - 1] * d[m] * d[j]);
}
System.out.println(cost[1][n]);
}
}Solve Matrix Chain Multiplication online · All practice problems