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)
