Cheapest Multiplication Order
Medium2-D Dynamic Programming
Problem
A numerics library must multiply a chain of matrices A1 · A2 · ... · An. Matrix Ai has dims[i - 1] rows and dims[i] columns, so dims has n + 1 entries. Multiplying a p × q matrix by a q × r matrix costs p · q · r scalar multiplications.
Matrix multiplication is associative, so you may parenthesise the chain however you like. Return the minimum total cost of computing the product.
Example 1
- Input:
- dims = [6, 20, 4, 15]
- Output:
- 840
(A1 · A2) · A3 costs 6·20·4 + 6·4·15 = 480 + 360 = 840, while A1 · (A2 · A3) costs 1200 + 1800 = 3000.
Example 2
- Input:
- dims = [4, 7]
- Output:
- 0
A single matrix needs no multiplication.
Example 3
- Input:
- dims = [2, 3, 4, 5]
- Output:
- 64
Constraints
- 2 ≤ dims.length ≤ 101
- 1 ≤ dims[i] ≤ 100
Hint
Show the first hint
Whatever the parenthesisation, there is a last multiplication. Where can it split the chain?
Walkthrough
How to approach it
01Clarify before coding
- Are the dimensions guaranteed compatible? Yes, by construction Ai's columns equal Ai+1's rows.
- Do we return the cost or the parenthesisation? The cost.
- Can the result overflow 32 bits? Up to 100 · 100³ = 10^8, which fits.
02Brute force
Enumerate every full parenthesisation recursively and evaluate its cost.
Cost: The number of parenthesisations is the Catalan number C(n - 1), about 4^n / n^1.5: astronomically large for n = 100.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.