GeeksforGeeks Hard

Matrix Chain Multiplication

Given matrix dimensions where matrix i is dims[i-1] x dims[i], find the fewest scalar multiplications needed to multiply the whole chain.

dpinterval-dp

Open on GeeksforGeeks ↗

02

Intuition

Matrix multiplication is associative, so every parenthesisation yields the same product — but the cost varies wildly, sometimes by orders of magnitude. The last multiplication performed splits the chain into a left half and a right half, each of which must already be reduced to a single matrix. So the cost of a chain is the cost of its two halves plus one final multiply of dims[i-1] x dims[k] x dims[j]. Trying every split point k gives the answer, and because both halves are strictly shorter, the table must be filled by increasing chain length rather than in reading order.

How to spot this pattern

Interval DP: the answer for a range depends on splitting it at every interior point and combining two smaller ranges. Iterating by increasing span guarantees both halves are already computed. Any problem phrased as "optimally parenthesise / partition a sequence" has this shape.

03

Approach

1

State over intervals

dp[i][j] = minimum multiplications to reduce matrices i..j to one matrix. A single matrix needs no work, so the diagonal is zero.

2

Try every split

dp[i][j] = min over k in i..j-1 of dp[i][k] + dp[k+1][j] + dims[i-1]·dims[k]·dims[j]. The last term is the cost of combining the two resulting matrices.

3

Fill by length, not by row

Every split reads shorter intervals, so iterate span = 2..n and slide i across. Filling row by row would read cells that are not final yet.

04

Solution & live demo

▶1class Solution:
▶2    def matrixChain(self, dims):
▶3        n = len(dims) - 1
▶4        dp = [[0] * (n + 1) for _ in range(n + 1)]
▶5        for span in range(2, n + 1):
▶6            for i in range(1, n - span + 2):
▶7                j = i + span - 1
▶8                best = float("inf")
▶9                for k in range(i, j):
▶10                    cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
▶11                    best = min(best, cost)
▶12                dp[i][j] = best
▶13        return dp[1][n]

05

Common pitfalls

Iterating by i and j rather than by span

✗ Wrong

for i in range(1, n+1):
    for j in range(i+1, n+1):

✓ Right

for span in range(2, n + 1):
    for i in range(1, n - span + 2):
        j = i + span - 1

dp[i][j] needs dp[i][k] and dp[k+1][j], both strictly shorter intervals. Plain nested loops over i and j read cells that haven't been filled yet, so the table is built from zeros.

Getting the cost formula's dimensions wrong

✗ Wrong

dims[i] * dims[k] * dims[j]

✓ Right

dims[i - 1] * dims[k] * dims[j]

Matrix i has dimensions dims[i-1] × dims[i], so the product of blocks i..k and k+1..j costs dims[i-1] × dims[k] × dims[j]. Using dims[i] shifts every factor and silently produces a plausible wrong number.

Letting k reach j

✗ Wrong

for k in range(i, j + 1):

✓ Right

for k in range(i, j):

The split puts i..k on the left and k+1..j on the right, so k = j leaves the right side empty and reads dp[j+1][j]. The last valid split point is j - 1.

06

Edge cases

Single matrix

dp[1][1] = 0 — nothing to multiply.

Two matrices

Exactly one split exists, so the answer is the single product dims[0]·dims[1]·dims[2].

Cost, not the product

The result is a multiplication count; the matrix product itself is identical under every parenthesisation.

07

Complexity

Time

O(n³)

Space

O(n²)

O(n²) intervals, each trying up to n split points. Catalan-many parenthesisations are collapsed into a quadratic table.