☕ DSA Java Articles

Topics › Dynamic Programming › MCM DP - Partition DP

Matrix Chain Multiplication - Bottom-Up - (DP-49)

Hard TUF ID 2806 A2Z

Java source ↗ Edit this article ↗

Problem

This is the bottom-up (tabulation) treatment of Matrix Chain Multiplication. The problem is the same: an array arr of length N describes N - 1 matrices, where matrix A_i has arr[i - 1] rows and arr[i] columns. Multiplying p × q by q × r costs p · q · r scalar multiplications. Choose the bracketing of A_1 A_2 ... A_{N-1} that minimises the total cost and return that cost. As an extension, we also print the optimal bracketing.

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

Example 1

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

Example 2

arr = [10, 20, 30]                  // two matrices: only one way to multiply
answer = 6000, bracketing (AB)

The recurrence

Let f(i, j) be the cheapest way to multiply A_i .. A_j. Look at the last multiplication: it joins the product of A_i .. A_k (an arr[i-1] × arr[k] matrix) with the product of A_{k+1} .. A_j (an arr[k] × arr[j] matrix). The two sides are independent, so

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]

The memoized version of this recursion is kept in the Java file as a reference for the tests. It is shown here so the conversion below can be compared line by line.

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++) {
        best = Math.min(best, memo(i, k, arr, dp) + memo(k + 1, j, arr, dp) + (long) arr[i - 1] * arr[k] * arr[j]);
    }
    return dp[i][j] = best;
}

From recursion to a table

The conversion follows the same three steps for every DP problem:

  1. Base cases first. The recursion returns 0 for i == j. In the table that is the diagonal dp[i][i] = 0, which a fresh Java long[][] already contains.
  2. Change the direction of the states. The recursion starts at the biggest range (1, N - 1) and calls smaller ones. The table must therefore be filled from small ranges to big ones, so that every lookup hits a finished cell.
  3. Copy the recurrence, replacing recursive calls with table lookups.

Step 2 is the only one that needs thought. A cell dp[i][j] reads two kinds of cells:

Any order that finishes the left part of a row and the lower part of a column before the cell itself is valid. Two such orders are common, and both are implemented below.

Approach 1: Tabulation, rows bottom to top

Intuition. Process i from N - 1 down to 1 so every lower row is complete, and inside a row process j from i + 1 upward so the cells to the left are complete. This is the order you get mechanically by reversing the recursion’s parameters: i started at 1 and moves right, so the loop runs it backwards; j started at N - 1 and moves left, so the loop runs it forwards.

Algorithm.

  1. Allocate dp[N][N].
  2. For i = N - 1 down to 1, for j = i + 1 to N - 1: set dp[i][j] to the minimum of the recurrence over k.
  3. Return dp[1][N - 1].
static long tabulation(int[] arr) {
    int n = arr.length;
    long[][] dp = new long[n][n];                           // base case dp[i][i] = 0 is the default
    for (int i = n - 1; i >= 1; i--) {
        for (int j = i + 1; j < n; j++) {
            dp[i][j] = Long.MAX_VALUE;
            for (int k = i; k < j; k++) {                   // dp[i][k] is left in row i, dp[k + 1][j] is below
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + (long) arr[i - 1] * arr[k] * arr[j]);
            }
        }
    }
    return dp[1][n - 1];
}

Complexity. Time O(N^3): O(N^2) cells, O(N) splits each. Space O(N^2).

Approach 2: Tabulation by chain length

Intuition. Every sub-range i..k and k + 1..j used by dp[i][j] is strictly shorter than i..j. So another valid order is to fill all ranges of length 2, then all of length 3, and so on. In the table this sweeps the diagonals parallel to the main one, moving towards the top-right corner. This is the order used in most textbooks, and it generalises to any interval DP where the split is not fixed to a row or column direction.

Algorithm.

  1. For len from 2 to N - 1 (the number of matrices in the range):
  2. For every start i such that the end j = i + len - 1 is at most N - 1, compute dp[i][j] from the recurrence.
  3. Return dp[1][N - 1].
static long tabulationByLength(int[] arr) {
    int n = arr.length;
    long[][] dp = new long[n][n];
    for (int len = 2; len < n; len++) {                     // number of matrices in the sub-chain
        for (int i = 1; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Long.MAX_VALUE;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + (long) arr[i - 1] * arr[k] * arr[j]);
            }
        }
    }
    return dp[1][n - 1];
}

Complexity. Same as Approach 1: O(N^3) time, O(N^2) space. The two methods compute exactly the same table; only the visiting order differs.

Approach 3: Recovering the bracketing

Intuition. The table holds costs, not decisions. To print the optimal order, remember the winning split for each cell in split[i][j]. Then rebuild the expression recursively: a single matrix prints its letter; a range prints (, the left part up to split[i][j], the right part, and ).

Algorithm.

  1. Fill dp as in Approach 1, and whenever a strictly cheaper split is found, store k in split[i][j].
  2. Call build(1, N - 1), which recurses on split and appends letters and brackets.
static String parenthesization(int[] arr) {
    int n = arr.length;
    long[][] dp = new long[n][n];
    int[][] split = new int[n][n];
    for (int i = n - 1; i >= 1; i--) {
        for (int j = i + 1; j < n; j++) {
            dp[i][j] = Long.MAX_VALUE;
            for (int k = i; k < j; k++) {
                long cost = dp[i][k] + dp[k + 1][j] + (long) arr[i - 1] * arr[k] * arr[j];
                if (cost < dp[i][j]) { dp[i][j] = cost; split[i][j] = k; }
            }
        }
    }
    StringBuilder sb = new StringBuilder();
    build(1, n - 1, split, sb);
    return sb.toString();
}

static void build(int i, int j, int[][] split, StringBuilder sb) {
    if (i == j) { sb.append((char) ('A' + i - 1)); return; }
    sb.append('(');
    build(i, split[i][j], split, sb);
    build(split[i][j] + 1, j, split, sb);
    sb.append(')');
}

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

cell candidates best split
dp[1][2] 40·20·30 24000 1
dp[2][3] 20·30·10 6000 2
dp[3][4] 30·10·30 9000 3
dp[1][3] k=1: 0 + 6000 + 8000; k=2: 24000 + 0 + 12000 14000 1
dp[2][4] k=2: 0 + 9000 + 18000; k=3: 6000 + 0 + 6000 12000 3
dp[1][4] k=1: 0 + 12000 + 24000; k=2: 24000 + 9000 + 36000; k=3: 14000 + 0 + 12000 26000 3

Rebuilding: split[1][4] = 3 gives ( + build(1, 3) + D + ). split[1][3] = 1 gives (A + build(2, 3) + ), and split[2][3] = 2 gives (BC). Together: ((A(BC))D).

Complexity. O(N^3) time to fill the tables and O(N) to rebuild the string. Space O(N^2) for dp and split.

Edge cases and pitfalls