matrix-chain multiplication

You have several matrices to multiply in a fixed left-to-right order, say A times B times C times D. Matrix multiplication is associative, so the answer is the same no matter how you parenthesize — (A B)(C D) or A((B C)D) all give the identical matrix. But the amount of arithmetic is not the same: multiplying a 10x100 by a 100x5 costs 10 times 100 times 5 = 5000 scalar multiplications, and a bad parenthesization can do orders of magnitude more work than a good one. The task is to find the cheapest way to parenthesize, not to actually multiply.

Encode the matrices by their dimensions: matrix i is p[i-1] by p[i], so a chain of matrices 1..n needs a dimension array p[0..n]. Let dp[i][j] be the minimum number of scalar multiplications to compute the product of matrices i through j. A single matrix needs none, so dp[i][i] = 0. For a longer chain you decide the last multiplication: split at k, first compute the left product (matrices i..k, which yields a p[i-1] by p[k] matrix) and the right product (matrices k+1..j, a p[k] by p[j] matrix), then multiply those two, costing p[i-1] times p[k] times p[j]. So dp[i][j] = min over k from i to j-1 of dp[i][k] + dp[k+1][j] + p[i-1] p[k] p[j]. This is the canonical interval DP: fill by increasing chain length so both sub-products are known.

There are O(n^2) intervals and O(n) splits each, giving O(n^3) time and O(n^2) space — and the table only finds the best cost, so you store the split points to reconstruct the actual parenthesization. This is the textbook illustration of why optimal substructure plus overlapping subproblems calls for DP rather than greedy: no simple greedy rule (like always multiply the smallest dimension first) is correct in general. The cost is the count of scalar multiplications under the schoolbook algorithm; using Strassen-style fast multiplication changes the cost model, but the ordering problem and its DP are the standard textbook version.