Split point

Find the best split point.

Split point k

For each m[i][j] a split point k is chosen: i ≤ k < j. Cost becomes m[i][k] + m[k+1][j] + dims[i-1]·dims[k]·dims[j].

All k values are tried and the smallest cost is picked. This is the optimal substructure property.

Recurrence relation

The recurrence: m[i][j] = min(m[i][k] + m[k+1][j] + dims[i-1]*dims[k]*dims[j]) over all k. Chain length is computed from short to long.

This formula solves overlapping subproblems once, reducing complexity to O(n³).

Exercise matrix_chain function

Write matrix_chain(dims). Fill the m table with nested loops, return m[1][n-1]. Print 18000 with print(matrix_chain(init_dims())).

Show example solution

def init_dims():
    # Return dimension array
    return [10, 20, 30, 40]
def matrix_chain(dims):
    # Find the lowest cost
    n = len(dims)
    m = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for i in range(1, n - length + 1):
            j = i + length - 1
            m[i][j] = float('inf')
            for k in range(i, j):
                cost = m[i][k] + m[k + 1][j] + dims[i - 1] * dims[k] * dims[j]
                if cost < m[i][j]:
                    m[i][j] = cost
    return m[1][n - 1]
print(matrix_chain(init_dims()))

Test yourself

Split point: match the terms

i≤k<j

Split range
dims

Dimension array
m[i][j]

Lowest cost
m[i][i]

0
What is the lowest cost for three matrices [10,20,30,40]?
- 6000
- 24000
- 18000
- 32000
Show answer

18000 — m[1][3] = 18000.

Inner loop variable

for k in range(i, ____):

Show answer

for k in range(i, j):

Next lesson: Summary - Matrix chain

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies