Summary - Matrix chain

Print the minimum multiplication cost in a mini task.

Summary - Matrix chain

In this group you learned to find the lowest cost of matrix chain multiplication with dynamic programming. Dimension array, DP table and split point combine into the solution.

Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.

Exercise min_chain_cost function

Write min_chain_cost(dims). Build the DP table, fill it with nested loops and return m[1][n-1]. Print 18000 with print(min_chain_cost([10, 20, 30, 40])).

Show example solution

def min_chain_cost(dims):
    # Find lowest cost with DP
    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(min_chain_cost([10, 20, 30, 40]))

Test yourself

Which table cell does matrix_chain return?
- m[0][0]
- m[0][n]
- m[n][n]
- m[1][n-1]
Show answer

m[1][n-1] — m[1][n-1] is the cost of the whole chain.
Dimension array
```
dims = init_____()
```
Show answer
```
dims = init_dims()
```
Summary - Matrix chain: match the terms

init_dims

Dimension
init_table

Table
matrix_chain

Cost
k

Split

Next lesson: All pairs

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies