Where you split a range matters
Try every place to split a range in two, and combine the best cost of each half plus the cost of joining them. About 14 minutes.
Think about the very last multiplication
With a row of blocks to multiply, some multiplication happens last. It joins everything to the left of some split point with everything to its right. Each side was multiplied out on its own first.
So the cheapest cost for a stretch of blocks is: try every split point, and for each one add the cheapest cost of the left part, the cheapest cost of the right part, and the price of the final join. Keep the smallest.
Short stretches first
Every stretch depends only on shorter stretches inside it. So fill the table by length: single blocks first (they cost nothing, there's nothing to multiply), then pairs, then threes, and so on up to the whole row.
This "by length" order is the signature of interval DP, and you'll see it in every step of this stage. For the four blocks in the example, the best grouping costs 30,000.
join = dims[i] * dims[k + 1] * dims[j + 1]
Each box is the cheapest way to multiply the blocks from its row's letter to its column's letter. A single block needs no multiplying, so the diagonal is all 0.
Three blocks. Splitting after the first costs 0 + 200 + 500 = 700 in total. Splitting after the second costs 300 + 0 + 400 = 700. What's the cheapest cost for all three?
- A700
- B1400
- C500
Show the answer
700. Both splits happen to cost 700, so the cheapest is 700.
Matrix chain multiplication
You get dims, describing n matrices: matrix i (0-indexed) has dims[i] rows and dims[i + 1] columns. Multiplying a p×q matrix by a q×r matrix costs p × q × r individual multiplications. Return the smallest total number of multiplications needed to multiply all n matrices together, in some grouping (the grouping doesn't change the final matrix, only the cost).
dims = [10, 20, 30, 40, 30] → 30000
0 ≤ n ≤ 500 (dims.length = n + 1) · 1 ≤ dims[i] ≤ 1,000 · return a long