☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Matrix chain multiplication

Hard TUF ID 327 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You are given an array arr of N positive integers describing a chain of N - 1 matrices: matrix A_i (for i from 1 to N - 1) has arr[i - 1] rows and arr[i] columns. Multiplying a p × q matrix by a q × r matrix takes p · q · r scalar multiplications and produces a p × r matrix.

Matrix multiplication is associative, so the product A_1 A_2 ... A_{N-1} is the same however we place the brackets, but the cost is not. The order of the matrices is fixed; only the bracketing is ours to choose. Return the minimum total number of scalar multiplications.

Constraints (GeeksforGeeks version): 2 ≤ N ≤ 100, 1 ≤ arr[i] ≤ 500.

Example 1

arr = [10, 20, 30, 40, 50]          // A 10x20, B 20x30, C 30x40, D 40x50
answer = 38000                      // (((AB)C)D) = 6000 + 12000 + 20000

Example 2

arr = [40, 20, 30, 10, 30]          // A 40x20, B 20x30, C 30x10, D 10x30
answer = 26000                      // ((A(BC))D) = 6000 + 8000 + 12000

In Example 2 the left-to-right order (((AB)C)D) would cost 24000 + 12000 + 12000 = 48000, almost twice as much. Multiplying B and C first collapses the large inner dimension 30 early.

The partition DP pattern

This problem is the template for a family called partition DP (or MCM DP). It is recognisable by four features:

  1. The answer is about a contiguous range i..j of the input.
  2. Some “last operation” splits the range at a point k into i..k and k + 1..j.
  3. Once the split is fixed, the two sides can be solved independently.
  4. The cost of the split depends only on i, k and j, plus the two sub-answers.

Here, think about the last multiplication performed on A_i .. A_j. It multiplies the product of A_i .. A_k by the product of A_{k+1} .. A_j for some k. Whatever brackets are used inside the left part, its product is an arr[i - 1] × arr[k] matrix; the right part is always arr[k] × arr[j]. So the final multiplication costs arr[i - 1] · arr[k] · arr[j] no matter how the parts were computed, and each part should be computed as cheaply as possible on its own. That independence is what makes the recurrence correct:

f(i, i) = 0
f(i, j) = min over k in [i, j - 1] of  f(i, k) + f(k + 1, j) + arr[i-1] · arr[k] · arr[j]
answer  = f(1, N - 1)

Approach 1: Recursion

Intuition. Implement the recurrence directly: for every range, try every last split and keep the cheapest. A single matrix needs no multiplication, which is the base case.

Algorithm.

  1. If i == j, return 0.
  2. For each k from i to j - 1, compute the cost of splitting there.
  3. Return the minimum.
static long recursive(int[] arr) {
    return solve(1, arr.length - 1, arr);
}

static long solve(int i, int j, int[] arr) {
    if (i == j) return 0;                                   // a single matrix costs nothing
    long best = Long.MAX_VALUE;
    for (int k = i; k < j; k++) {                           // (A_i .. A_k) times (A_k+1 .. A_j)
        long cost = solve(i, k, arr) + solve(k + 1, j, arr) + (long) arr[i - 1] * arr[k] * arr[j];
        best = Math.min(best, cost);
    }
    return best;
}

Complexity. Time exponential: the number of bracketings of m matrices is the Catalan number C(m - 1), which grows roughly like 4^m, and the recursion explores all of them. Space O(N) for the recursion depth.

The costs are accumulated in long. With 100 matrices of size 500 × 500, any bracketing costs 99 · 500^3 ≈ 1.24 × 10^10, which overflows int. The multiplication (long) arr[i - 1] * arr[k] * arr[j] is cast before the first product so the whole expression is evaluated in long.

Approach 2: Memoization

Intuition. The recursion keeps solving the same ranges: f(2, 3) is needed by f(1, 3), by f(2, 4), and by many larger ranges. There are only O(N^2) pairs (i, j), so store each result in dp[i][j] the first time it is computed. All costs are non-negative, so -1 safely marks “not computed yet”.

Algorithm.

  1. Fill dp with -1.
  2. In the helper, return 0 for a single matrix and the cached value if present; otherwise compute it as in Approach 1 and store it.
static long memoization(int[] arr) {
    int n = arr.length;
    long[][] dp = new long[n][n];
    for (long[] row : dp) Arrays.fill(row, -1);
    return memo(1, n - 1, arr, dp);
}

static long memo(int i, int j, int[] arr, long[][] dp) {
    if (i == j) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    long best = Long.MAX_VALUE;
    for (int k = i; k < j; k++) {
        long cost = memo(i, k, arr, dp) + memo(k + 1, j, arr, dp) + (long) arr[i - 1] * arr[k] * arr[j];
        best = Math.min(best, cost);
    }
    return dp[i][j] = best;
}

Complexity. Time O(N^3): O(N^2) states, each trying O(N) split points. Space O(N^2) for the table plus O(N) stack.

Approach 3: Tabulation

Intuition. To fill the table without recursion we need an order in which every cell’s dependencies are already computed. dp[i][j] reads dp[i][k] with k < j, which is in the same row, to the left, and dp[k + 1][j] with k + 1 > i, which is in a lower row, same column. So process rows from the bottom (i = N - 1) up to i = 1, and inside each row move left to right (j = i + 1 .. N - 1). The diagonal dp[i][i] = 0 is the base case and is already zero in a new Java array.

Algorithm.

  1. Create dp of size N × N (all zeros).
  2. For i from N - 1 down to 1, for j from i + 1 to N - 1, set dp[i][j] to the minimum over k of the recurrence.
  3. Return dp[1][N - 1].
static long tabulation(int[] arr) {
    int n = arr.length;
    long[][] dp = new long[n][n];                           // dp[i][i] = 0 already
    for (int i = n - 1; i >= 1; i--) {
        for (int j = i + 1; j < n; j++) {
            long best = Long.MAX_VALUE;
            for (int k = i; k < j; k++) {
                best = Math.min(best, dp[i][k] + dp[k + 1][j] + (long) arr[i - 1] * arr[k] * arr[j]);
            }
            dp[i][j] = best;
        }
    }
    return dp[1][n - 1];
}

Dry run on Example 1, arr = [10, 20, 30, 40, 50]:

cell candidates (one per k) value
dp[3][4] 30·40·50 60000
dp[2][3] 20·30·40 24000
dp[2][4] k=2: 0 + 60000 + 30000; k=3: 24000 + 0 + 40000 64000
dp[1][2] 10·20·30 6000
dp[1][3] k=1: 0 + 24000 + 8000; k=2: 6000 + 0 + 12000 18000
dp[1][4] k=1: 0 + 64000 + 10000; k=2: 6000 + 60000 + 15000; k=3: 18000 + 0 + 20000 38000

The winning split for the full chain is k = 3, which means (A B C) times D, and inside that k = 2, giving ((AB)C)D.

Complexity. Time O(N^3), about N^3 / 6 inner steps. Space O(N^2).

Unlike many DP problems, there is no useful space optimisation: dp[i][j] reads its whole row to the left and its whole column below, so the full table must be kept.

Edge cases and pitfalls