Split point
- Algorithms course
- Advanced
- Lesson 23/56
- 4 min
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³).
Practice 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())).
Starter code
def init_dims():
# Return dimension array
return [10, 20, 30, 40]
def matrix_chain(dims):
# Find the lowest costSample 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()))Expected output
18000
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Split point: match the terms
| Term | Meaning |
|---|---|
i≤k<j |
Split range |
dims |
Dimension array |
m[i][j] |
Lowest cost |
m[i][i] |
0 |
2 What is the lowest cost for three matrices [10,20,30,40]?
- 6000
- 24000
- 18000 Correct answer
- 32000
Explanation: m[1][3] = 18000.
3 Inner loop variable
Question
for k in range(i, ____):
Answer
for k in range(i, j):Explanation: j is right.