Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The last multiplication splits the chain i..j into (i..m) × (m+1..j) for some m.
  2. 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