Matrix Chain Multiplication

Matrices: A(2,3) B(3,6) C(6,4) D(4,5)

Array = [2, 3, 6, 4, 5]

init:

row/col	0	1	2	3
0	0
1		0
2			0
3				0

---

Length 2

A*B = 2 * 3 * 6 = 36

B*C = 3 * 6 * 4 = 72

C*D = 6 * 4 * 5 = 120

row/col	0	1	2	3
0	0	36
1		0	72
2			0	120
3				0

---

Length 3

A * B * C

• (AB)C = 36 + 2 * 6 * 4 = 36 + 48 = 84 min
• A(BC) = 2 * 3 * 4 + 72 = 24 + 72 = 96

B * C * D

• B(CD) = 3 * 6 * 5 + 120 = 210
• (BC)D = 72 + 3 * 4 * 5 = 132 min

row/col	0	1	2	3
0	0	36	84
1		0	72	132
2			0	120
3				0

---

Length 4

A * B * C * D

• A(BCD) = 2 * 3 * 5 + 132 = 162
• (ABC)D = 84 + 2 * 4 * 5 = 124 min
• (AB)(CD) = 36 + 120 + 2 * 6 * 5

row/col	0	1	2	3
0	0	36	84	124
1		0	72	132
2			0	120
3				0

---

minimum operation 124