• 2 ≤ dims.length ≤ 100, so there are at most 99 matrices
• 1 ≤ dims[i] ≤ 100
• The order of the matrices in the chain is fixed and may not be rearranged
• Only the grouping — where the parentheses go — is yours to choose

Multiplying a p × q matrix by a q × r matrix takes p × q × r scalar multiplications — one for each cell of the p × r result, times the q terms summed into it. The order of the matrices in the chain is fixed and cannot be shuffled, but because matrix multiplication is associative, you may choose where the parentheses go, and different groupings cost wildly different amounts while producing the identical result.

Take three matrices A (1 × 2), B (2 × 3), C (3 × 4).

Nearly twice the work for the same answer. On longer chains the gap becomes enormous, which is why compilers and numerical libraries genuinely solve this problem.

The dimensions are given as a single array because adjacent matrices must agree: if matrix i is dims[i-1] × dims[i], then matrix i+1 starts with dims[i] rows automatically. One array of n+1 numbers encodes n matrices with no possibility of a mismatch.

"Always multiply the cheapest adjacent pair first" seems reasonable. It is wrong, because the cheap multiplication you perform now leaves behind a result matrix whose shape determines the cost of everything afterwards. A cheap step can leave a fat matrix that poisons the rest of the chain, and an expensive step can leave a thin one that makes everything after it cheap.

Enumerating every parenthesisation is not an option either — the number of ways to bracket n matrices is the Catalan number, which grows roughly like 4ⁿ. For 99 matrices that is beyond astronomical.

Here is the trick. The other problems walked along one element at a time, but a chain has no natural "next" — the grouping is a tree, not a walk. So instead of the first step, I think about the last one.

Say I want to multiply matrices i through j. However I bracket them, there is exactly one multiplication I do last, and it joins a left block with a right block. That last step splits the chain at some k: matrices i..k are already collapsed into one matrix, matrices k+1..j into another, and I multiply those two.

I don't know the best k, so I try every split from i to j-1, solve each side the same way, and keep the cheapest.

Why can the two sides be solved separately? Because their shapes are fixed no matter how each is bracketed inside: block i..k is dims[i-1] × dims[k], block k+1..j is dims[k] × dims[j]. So the final multiply always costs dims[i-1] × dims[k] × dims[j], and the two sub-costs simply add.

f(i, j) = min over k from i to j-1 of [ f(i, k) + f(k+1, j) + dims[i-1] × dims[k] × dims[j] ]

Base case: f(i, i) = 0 — a single matrix needs no multiplication. The answer is f(1, n).

Write the story down as plain recursion — it simply tries every split:

def matrix_chain(dims):
    n = len(dims) - 1              # number of matrices

    def f(i, j):
        if i == j: return 0                       # single matrix: nothing to do
        best = float('inf')
        for k in range(i, j):                     # last multiplication splits after k
            cost = f(i, k) + f(k + 1, j) + dims[i - 1] * dims[k] * dims[j]
            best = min(best, cost)
        return best

    return f(1, n)

Correct, but it re-solves the same intervals again and again — the number of bracketings is Catalan-many, roughly 4ⁿ. Yet there are only about N²/2 different (i, j) intervals. So keep a notebook and solve each once:

def matrix_chain(dims):
    n = len(dims) - 1
    memo = {}

    def f(i, j):
        if i == j: return 0
        if (i, j) in memo: return memo[(i, j)]
        best = float('inf')
        for k in range(i, j):
            cost = f(i, k) + f(k + 1, j) + dims[i - 1] * dims[k] * dims[j]
            best = min(best, cost)
        memo[(i, j)] = best
        return best

    return f(1, n)

Turn it into a table. Let dp[i][j] hold what f(i, j) returned, and swap each call for an array read:

dp[i][j] = min over k of [ dp[i][k] + dp[k+1][j] + dims[i-1] × dims[k] × dims[j] ]

Now the fill order — and this is where interval problems differ. dp[i][j] reads dp[i][k] and dp[k+1][j], both covering shorter stretches of the chain, but one has a larger i and the other a smaller j. Neither index moves consistently, so no plain ascending or descending loop works. What always shrinks, though, is the interval length. So loop by length, shortest first — then every sub-interval a cell needs is already filled. The base case dp[i][i] = 0 is the length-1 diagonal, and the answer is dp[1][n]:

def matrix_chain(dims):
    n = len(dims) - 1
    dp = [[0] * (n + 1) for _ in range(n + 1)]     # dp[i][i] = 0 already

    for length in range(2, n + 1):                 # chains of 2, then 3, ...
        for i in range(1, n - length + 2):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = (dp[i][k] + dp[k + 1][j]
                        + dims[i - 1] * dims[k] * dims[j])
                dp[i][j] = min(dp[i][j], cost)

    return dp[1][n]

Length 2:
- f(1,2) — only split k = 1: 0 + 0 + (1 × 2 × 3) = 6
- f(2,3) — only split k = 2: 0 + 0 + (2 × 3 × 4) = 24

Length 3:
- f(1,3), two splits to try:
- k = 1, meaning A(BC): f(1,1) + f(2,3) + 1 × 2 × 4 = 0 + 24 + 8 = 32
- k = 2, meaning (AB)C: f(1,2) + f(3,3) + 1 × 3 × 4 = 6 + 0 + 12 = 18

Answer 18, matching the hand calculation at the top of the page. And notice that the winning split reused f(1,2) = 6, computed once and consulted here — the whole reason for the table.

A longer one, dims = [40, 20, 30, 10, 30]: the table works up through lengths 2 and 3 and settles at 26000, against 120000 for the worst bracketing. The best grouping multiplies the middle pair down to a thin 20 × 10 matrix first, so that the expensive outer dimensions are only ever combined through a small shared dimension.

This is a different animal from everything earlier in the section, and recognising it is what matters.

The signal: the answer for a stretch of the input is built from the answers for two adjacent sub-stretches, and you get to choose where they meet. The input is a sequence, but the solution is a tree of pairings rather than a walk from one end to the other.

The state: an interval (i, j) — a left and a right boundary — rather than a single position.

The choice: the split point k inside the interval, tried exhaustively.

The loop order: by interval length, shortest first.

The typical cost: O(N³), from N² intervals times N split points.

The step that takes practice is finding the right thing to fix. Here we fixed the last multiplication, and that worked because it left two independent blocks whose shapes were already known. Fixing the first multiplication instead would have been a disaster — after multiplying one adjacent pair, the chain changes shape and the remaining problem is no longer a clean sub-interval of the original. When you set up an interval table, always ask: what can I fix so that what remains falls into independent pieces of the same kind?

Others in this family use the same skeleton with a different combining rule: the longest palindromic subsequence, minimum insertions to make a palindrome, optimal binary search trees, and scoring games where two players take from the ends of a row. Whenever the input is a sequence but the solution is a tree of pairings, reach for an interval (i, j) state and try every split inside it.