The Cheapest Way to Multiply a Chain
A chain of n matrices is given by n + 1 dimensions: matrix i has p[i-1] rows and
p[i] columns. Multiplying an a by b matrix with a b by c matrix costs a * b * c
scalar multiplications.
Matrix multiplication is ASSOCIATIVE, so the product can be bracketed any way, and different bracketings cost different amounts. Print the smallest total cost.
dimensions 40 20 30 10 30 -> 26000
dimensions 10 20 30 -> 6000 only one way to bracket two matrices
## Why greedy fails
Multiplying the cheapest adjacent pair first is the obvious rule and it is wrong, because a cheap product can leave behind a matrix with an awkward shape that makes everything after it expensive. The cost of a choice is not local.
## The state is an INTERVAL
A bracketing of the whole chain splits it at some position into two bracketed sub-chains. Each sub-chain is a CONTIGUOUS run of matrices, never a scattered set, because multiplication only combines neighbours.
So the state is a range:
dp[i][j] = the cheapest way to multiply matrices i through j
That is the defining feature of this whole topic. In a linear DP the state is a prefix; here it is an interval, because the object being built has a recursive structure over ranges.
## The recurrence
dp[i][i] = 0
dp[i][j] = min over k in i..j-1 of dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]
The last term is the cost of the FINAL multiplication, which combines a p[i-1] by p[k]
result with a p[k] by p[j] result.
Getting those three indices right is most of the implementation. p[i-1] is the row count
of the first matrix in the range, and p[j] is the column count of the last.
## Fill by increasing length
dp[i][j] depends on dp[i][k] and dp[k+1][j], both SHORTER ranges. So the loop is over
length:
for length in 2..n:
for i in 1..n-length+1:
j = i + length - 1
A plain nested loop over i then j reads entries that have not been written, which in a
zero-initialised table silently understates every answer.
That fill order is what every problem in this topic shares, and it is the first thing to check when an interval DP returns something too small.
## Boundaries
A single matrix costs 0, which is why 1 2 answers 0: there is nothing to multiply.
3 3 3 3 answers 54, three identical 3 by 3 matrices, where every bracketing costs the
same. That input confirms the recurrence does not accidentally favour one split.
## Cost
Time O(n^3). Space O(n^2).
Costs reach 500^3 times 100, so accumulate in 64 bits.