This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Do we just want to calculate the cost and not list the actual order of operations?
• Yes
• Can we assume the inputs are valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None -> Exception
• [] -> 0
• [Matrix(2, 3), Matrix(3, 6), Matrix(6, 4), Matrix(4, 5)] -> 124

## Algorithm¶

We'll use bottom up dynamic programming to build a table.

  0    1    2    3
[2,3][3,6][6,4][4,5]

Case: 0 * 1
2 * 3 * 6 = 36

Case: 1 * 2
3 * 6 * 4 = 72

Case: 2 * 3
6 * 4 * 5 = 120

Case: 0 * 1 * 2
0 * (1 * 2) = 2 * 3 * 4 + 72 = 96
(0 * 1) * 2 = 36 + 2 * 6 * 4 = 84
min: 84

Case: 1 * 2 * 3
1 * (2 * 3) = 3 * 6 * 5 + 120 = 210
(1 * 2) * 3 = 72 + 3 * 4 * 5 = 132
min: 132

Case: 0 * 1 * 2 * 3
0 * (1 * 2 * 3) = 2 * 3 * 5 + 132 = 162
(0 * 1) * (2 * 3) = 36 + 120 + 2 * 6 * 5 = 216
(0 * 1 * 2) * 3 = 84 + 2 * 4 * 5 = 124
min: 124

---------------------
| 0 |  1 |  2 |   3 |
---------------------
0 | 0 | 36 | 84 | 124 |
1 | x |  0 | 72 | 132 |
2 | x |  x |  0 | 120 |
3 | x |  x |  x |   0 |
---------------------

min cost = T[0][cols-1] = 124

for k in range(i, j):
T[i][j] = minimum of (T[i][k] + T[k+1][j] +
m[i].first * m[k].second * m[j].second) for all k


### Explanation of k¶

  0    1    2    3
[2,3][3,6][6,4][4,5]

Fill in the missing cell, where i = 0, j = 3

---------------------
| 0 |  1 |  2 |   3 |
---------------------
0 | 0 | 36 | 84 | ??? |
1 | x |  0 | 72 | 132 |
2 | x |  x |  0 | 120 |
3 | x |  x |  x |   0 |
---------------------

Case: 0 * (1 * 2 * 3), k = 0
i = 0, j = 3

0 * (1 * 2 * 3) = 2 * 3 * 5 + 132 = 162
T[i][k] + T[k+1][j] + m[i].first * m[k].second * m[j].second
T[0][0] + T[1][3] + 2 * 3 * 5
0 + 132 + 30 = 162

Case: (0 * 1) * (2 * 3), k = 1
i = 0, j = 3

(0 * 1) * (2 * 3) = 36 + 120 + 2 * 6 * 5 = 216
T[i][k] + T[k+1][j] + m[i].first * m[k].second * m[j].second
T[0][1] + T[2][3] + 2 * 6 * 5
36 + 120 + 60 = 216

Case: (0 * 1 * 2) * 3, k = 2
i = 0, j = 3

(0 * 1 * 2) * 3 = 84 + 2 * 4 * 5 = 124
T[i][k] + T[k+1][j] + m[i].first * m[k].second * m[j].second
T[0][2] + T[3][3] + 2 * 4 * 5
84 + 0 + 40 = 124



Complexity:

• Time: O(n^3)
• Space: O(n^2)

## Code¶

In [1]:
class Matrix(object):

def __init__(self, first, second):
self.first = first
self.second = second

In [2]:
import sys

class MatrixMultiplicationCost(object):

def find_min_cost(self, matrices):
if matrices is None:
raise TypeError('matrices cannot be None')
if not matrices:
return 0
size = len(matrices)
T = [[0] * size for _ in range(size)]
for offset in range(1, size):
for i in range(size-offset):
j = i + offset
min_cost = sys.maxsize
for k in range(i, j):
cost = (T[i][k] + T[k+1][j] +
matrices[i].first *
matrices[k].second *
matrices[j].second)
if cost < min_cost:
min_cost = cost
T[i][j] = min_cost
return T[0][size-1]


## Unit Test¶

In [3]:
%%writefile test_find_min_cost.py
import unittest

class TestMatrixMultiplicationCost(unittest.TestCase):

def test_find_min_cost(self):
matrix_mult_cost = MatrixMultiplicationCost()
self.assertRaises(TypeError, matrix_mult_cost.find_min_cost, None)
self.assertEqual(matrix_mult_cost.find_min_cost([]), 0)
matrices = [Matrix(2, 3),
Matrix(3, 6),
Matrix(6, 4),
Matrix(4, 5)]
expected_cost = 124
self.assertEqual(matrix_mult_cost.find_min_cost(matrices), expected_cost)
print('Success: test_find_min_cost')

def main():
test = TestMatrixMultiplicationCost()
test.test_find_min_cost()

if __name__ == '__main__':
main()

Overwriting test_find_min_cost.py

In [4]:
%run -i test_find_min_cost.py

Success: test_find_min_cost