Matrix Chain Multiplication
Hard · Dynamic Programming · about 30 minutes
Asked at Google, Microsoft, Amazon.
Matrix i has dimensions dims[i] × dims[i+1] (so dims describes a chain of len(dims) - 1 matrices). Multiplying a p × q matrix by a q × r matrix costs p·q·r scalar multiplications. Return the minimum total cost to multiply the whole chain, choosing the best parenthesization. A single matrix costs 0.