# Matrix Multiplication Parenthesization

Question

Example

Pic - subproblem tree, memo table, topo order

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-Ltpq_64jnFzaSoRaEXw%2Fmatrix%20mul1.jpg?generation=1573935273191058\&alt=media)

![](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LtpqP4Bii7DT_BTd4fN%2F-LtpqQ7GPCPppH_fyCKt%2F-Ltpq_66sB6NP8VbRY_S%2Fmatrix%20mul2.jpg?generation=1573935273010630\&alt=media)

Analysis - substring

Recurrence

going from outermost

```
DP(i, j) = min { DP(i, k) + DP(k, j) + Cost(A[i:k] * A[k:j]) }
           for k from i to j
We want to find the splitting point k where the cost is the minimum
```

Top-down

```
Initialization
for all j >= i, C(i, j) = 0 //half table is 0

// the topological order is increasing substring size s
// we go diagonally
for (s from 1 to n-1)
    for (i from 1 to n-s)
      j = i + s
      C(i, j) = min {C(i, k) + C(k+1, j) + Cost(A[i:k] * A[k+1:j]) for i <= k <= j}
return C(1, n)
```

O(n^2) subproblems and O(n) to compute each subproblem so O(n^3)

Bottom-up

## References

6.006 [Lecture 21 Notes](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21_orig.pdf)