Optimal grouping of a matrix product

A matrix is a rectangular array of numbers. The product of two matrices, $M_1 M_2$ is defined, so long as $M_1$ has the same number of columns as $M_2$ has rows. Suppose $M_1$ has $r_1$ rows and $c_1$ columns, $M_2$ has $r_2$ rows and $c_2$ columns ($c_1$ must equal $r_2$), then the product $M_1 M2$ requires $r_1 r_2 c_2$ multiplications of array elements. Matrix multiplication is associative (although not commutative), so three or more matrices can be multiplied (so long as the appropriate adjacent dimensions match):

$$M_1 M_2 M_3 = (M_1 M_2) M_3 = M_1 (M_2 M_3).$$

Although the value of $M_1 M_2 M_3$ is the same whichever way you group them, the amount of work (multiplications of array elements) is not. For example, suppose $M_1$ is a $2\times 3$ matrix (2 rows, 3 columns), $M_2$ is $3\times 4$, and $M_3$ is $4\times 5$. Then the grouping $(M_1\times M_2) M_3$ costs: $24 + 40$ $=$ $64$ multiplications. The grouping $M_1 (M_2 M_3)$ costs: $60 + 30$ $=$ $90$ multiplications. This disparity gets worse for longer chains of matrices. What is the best way to group

$$M_0 M_1 \ldots M_k ?$$

Here is a first attempt at finding a minimum-cost grouping. In analogy with triangulation, denote the minimum cost of grouping matrices $M_0\ldots M_k$ as $c[0][k]$, and the product $r_0 r_j c_k$ as $w(i,j,k)$. Then for each choice of $j$ with $0 \leq j < k$ we check the value of $c[0][j-1] + c[j][k] + w(i,j,k)$, and take the minimum. This formula looks close to that for triangulation except for two things: the first part of the sum is $c[0][j-1]$ rather than $c[0][j]$ (since the matrices don't overlap), and the function $w(i,j,k)$ is different.

You can fix the first problem by changing notation slightly. Define $c[i][k]$ to be the minimum cost of grouping matrices $M_0 \ldots M_{k-1}$ (instead of $M_0$ $\cdots$ $M_k$), so $w(i,j,k)$ $=$ $r_i r_j c_{k-1}$, and our recursive formula is now the same as Equation 1, except for $w(i,j,k)$ being different (and aren't there C++ features that might help with that?). You can use the same algorithm for both problems. The cost of a minimal grouping of matrices $M_0$ $\cdots$ $M_n$ is $c[0][n+1]$.