A graphics engine multiplies a chain of matrices M0 * M1 * ... * M(n-1). Matrix Mi has dims[i] rows and dims[i+1] columns. Multiplying a p x q matrix by a q x r matrix costs p * q * r scalar multiplications. Matrix multiplication is associative, so you may choose where to put the brackets. Return the smallest total cost of computing the whole product.
Examples
Input: dims = [4, 10, 3, 12]
Output: 264
Explanation: (M0 * M1) costs 4*10*3 = 120, then multiplying by M2 costs 4*3*12 = 144.
The other order costs 10*3*12 + 4*10*12 = 840.
Input: dims = [5, 7]
Output: 0
Explanation: a single matrix needs no multiplication.
Constraints
2 <= len(dims) <= 101(so up to 100 matrices)1 <= dims[i] <= 100- The number of bracketings grows like the Catalan numbers; aim for O(n**3).
Goals
- Choose the last multiplication that splits a chain into two parts
- Fill an interval table by increasing chain length