GeeksforGeeks: Hard2-D Dynamic Programming

Matrix Chain Multiplication

Problem in Plain English

Find the fewest scalar multiplications needed to multiply a chain of matrices described by a dimension array. Choose parentheses without changing matrix order.

Problem Statement

Given dimension array arr, matrix Mi has dimensions arr[i-1] × arr[i] for i = 1 through arr.length-1. Return the minimum scalar multiplication count over all parenthesizations. Multiplying an a × b matrix by a b × c matrix costs a × b × c scalar multiplications. You need the cost, not the product matrices or the parentheses.

Constraints

2 <= arr.length <= 100.
1 <= arr[i] <= 200.
Matrix order is fixed; only parentheses may change.

Examples

Example 1

Input: arr = [2,1,3,4]
Output: 20

The split after M1 costs 1 × 3 × 4 + 2 × 1 × 4 = 20; the split after M2 costs 2 × 1 × 3 + 2 × 3 × 4 = 30.

Example 2

Input: arr = [3,4]
Output: 0

There is one 3 × 4 matrix. No multiplication is performed.

Example 3

Input: arr = [1,2,3,4,3]
Output: 30

Left-associated products cost 6, then 12, then 12 scalar operations, totaling 30, the minimum over all splits.

Intuition

The final multiplication divides any parenthesized chain into two contiguous chains. Their result dimensions depend only on the endpoints, so try every final split and reuse the cheapest subchains. For Example 1, multiplying the last two matrices first costs 12, then multiplying the first matrix by that result costs 8, totaling 20. Multiplying the first two first costs 6 plus 24, totaling 30. A locally cheap multiplication can therefore lead to a more expensive complete chain.

Approaches

Interval DP

Optimal

Solution Details

Reveal Interval DP: intuition, complexity, and code

Intuition

Store the minimum cost for every contiguous matrix interval and fill shorter intervals before longer ones. Index matrices from 1: dp[i][j] is the cost of Mi through Mj, with dp[i][i] = 0. Split after Mk for every i <= k < j. The candidate is dp[i][k] + dp[k+1][j] + arr[i-1] × arr[k] × arr[j]. The two subchains are shorter than the interval being filled, so increasing chain length makes both available. This replaces repeated evaluation of exponentially many parenthesizations with a cubic table computation.

Step-by-Step Logic

Initialize singleton intervals dp[1][1], dp[2][2], dp[3][3] to 0.
Length 2: dp[1][2] = 2 × 1 × 3 = 6.
Length 2: dp[2][3] = 1 × 3 × 4 = 12.
Length 3, split k = 1: candidate 0 + 12 + 2 × 1 × 4 = 20.
Split k = 2: candidate 6 + 0 + 2 × 3 × 4 = 30; retain 20.
Return dp[1][3] = 20.

Why It Works

Every legal complete parenthesization has a unique final split k. Its left and right products have dimensions arr[i-1] × arr[k] and arr[k] × arr[j]. If either side used a more expensive parenthesization than its optimum, replacing it would reduce the total without changing dimensions. Thus an optimum uses optimal subchains, and trying all k includes its final split. Induction on interval length proves the recurrence: singleton intervals cost zero, and all shorter intervals are correct before a longer interval is evaluated. Taking the minimum yields exactly the optimum.

Dry Run

Interval DP: variable states at each step
Interval	Split	Subchain cost	Final multiply	Best
[1,1], [2,2], [3,3]	none	0	0	0
[1,2]	1	0 + 0	6	6
[2,3]	2	0 + 0	12	12
[1,3]	1	0 + 12	8	20
[1,3]	2	6 + 0	24	20
Return	none	complete chain	none	20

Complexity Analysis

Time Complexity

O(n^3)

Space Complexity

O(n^2)

For n matrices there are quadratic intervals and at most n splits per interval. The table is quadratic and the code is iterative. Each of the n-1 multiplications costs at most 200^3; with n at most 99, every candidate is at most 784,000,000, within Java int and exact JavaScript Number range.

Code

Solution.java

1class Solution {2    static int matrixMultiplication(int[] arr) {3        int n = arr.length - 1;4        int[][] dp = new int[n + 1][n + 1];5        for (int length = 2; length <= n; length++) {6            for (int i = 1; i + length - 1 <= n; i++) {7                int j = i + length - 1;8                dp[i][j] = Integer.MAX_VALUE;9                for (int k = i; k < j; k++) {10                    int cost = dp[i][k] + dp[k + 1][j]11                             + arr[i - 1] * arr[k] * arr[j];12                    dp[i][j] = Math.min(dp[i][j], cost);13                }14            }15        }16        return dp[1][n];17    }18}

Hints

Hint 1

Identify the last multiplication in a parenthesized chain.

Hint 2

Its split separates two contiguous subchains with fixed result dimensions.

Hint 3

Minimize over k and fill intervals by increasing length; a single matrix costs zero.

Edge Cases

Two dimensions describe one matrix and return zero, not the product of the dimensions.
Equal dimensions give equal costs for all parenthesizations, so no tie reconstruction is needed.
The maximum dimension array length requires all interval lengths through 99.

Common Mistakes and Interview Tips

Using arr[i] instead of arr[i-1] for the left row count changes the matrix dimensions.
Allowing k = j makes the right subchain empty and breaks the recurrence.
Filling i and j in an arbitrary order reads unfinished subchains.
Choosing the cheapest adjacent multiply greedily fails on Example 1.

Key Takeaway

When a final operation splits a fixed-order structure, define an interval state and enumerate that final split. Evaluate states in a dependency order and charge only the work done after the subproblems.