CodeBlanks Logo Icon CodeBlanks
Login Register

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.

Practice 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])).

Starter code

solution.py
def min_chain_cost(dims):
    # Find lowest cost with DP

Sample solution

solution.py
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]))

Expected output

18000

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Which table cell does matrix_chain return?

  • m[0][0]
  • m[0][n]
  • m[n][n]
  • m[1][n-1] Correct answer

Explanation: m[1][n-1] is the cost of the whole chain.

2 Dimension array

Question 
dims = init_____()
Answer 
dims = init_dims()

Explanation: dims is right.

3 Summary - Matrix chain: match the terms

Term Meaning
init_dims Dimension
init_table Table
matrix_chain Cost
k Split

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4