P30 · 1 second · 256 MB
Matrix Chain
`dims` has length `n+1`. There are `n` matrices; matrix `i` is `dims[i] × dims[i+1]`. Return the minimum number of scalar multiplications needed to compute the product. `n = 0` or `n = 1` costs 0.
function matrixChain(dims) → number
CONSTRAINTS
- 1 ≤ dims.length ≤ 41
- 1 ≤ dims[i] ≤ 100
Input: dims = [10, 20, 30, 40]
Output: 18000
(AB)C: 10*20*30 + 10*30*40 = 18000 beats A(BC).
Input: dims = [5, 10]
Output: 0
One matrix. No multiply.
1
2
3
4
5
6
7
8
Arena judges JavaScript in a Web Worker (1s wall-clock, then TLE). Samples are public; submit runs hidden tests too. C++/Python is a later swarm package.