Matrix Multiplication Parenthesization

Question

Example

Pic - subproblem tree, memo table, topo order

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