Matrix Chain Multiplication
You must multiply a chain of n matrices where matrix i has dimensions p[i-1] × p[i]. The product is fixed but the parenthesization is free. Return the minimum number of scalar multiplications needed.
- 2 ≤ p.length ≤ 500
- 1 ≤ p[i] ≤ 1000
- Cost depends on where you place the last split
- Subproblems are contiguous ranges of matrices
- Interval DP with a split point
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let cost[i][j] be the cheapest way to multiply matrices i..j. For each split k in [i, j), the cost is cost[i][k] + cost[k+1][j] + p[i-1] · p[k] · p[j]; take the minimum. Single matrices cost 0. Fill in order of increasing chain length so that both halves are known when needed, and return cost[1][n].
- Hu–Shing solves it in O(n log n) but is intricate. The Knuth optimization does not apply because the cost function lacks the required monotonicity.