Let's write the algorithm using the convention that we begin counting from 0, so we consider matrices through , has dimensions , has dimensions , etc. The most natural approach would be a recursive function (supposing we have an array with , ...):
int rec_matrix_product(int i, int j, int *s) { if (i == j) { return 0; } else { int C = rec_matrix_product(i, i, s) + rec_matrix_product(i+1, j, s) + s[i]*s[i+1]*s[j+1]; for (int k = i+1; k < j; k++) { int c = rec_matrix_product(i, k, s) + rec_matrix_product(k+1, j, s) + s[i]*s[k+1]*s[j+1]; if (c < C) C = c; } return C; } }If we solve the recurrence for the running time of the above code, we find that is still exponential, so we haven't made any progress from ! We need to solve this problem ``bottom-up.'' If we start along the diagonal where , the problem is easy, since is zero. Then we work on the diagonal where , and so on:
for (int i = 0; i < n; i++) C[i][i] = 0; for (int len = 1; len < n; len++) { for (int i = 0; i < n - len; i++) { int j = i + len; C[i][j] = C[i][i] + C[i+1][j] + s[i]*s[i+1]*s[j+1]; for (int k = i+1; k < j; k++) { if (C[i][k] + C[k+1][j] + s[i]*s[k+1]*s[j+1] < C[i][j]) C[i][j] = C[i][k] + C[k+1][j] + s[i]*s[k+1]*s[j+1]; } } }
Now we know the cost of a best grouping, but we need to recover grouping itself. You could work backwards from the optimal cost, and find two subcosts that would yield that number, but it's probably more straightforward just to keep track of the best groupings at each step:
for (int i = 0; i < n; i++) { C[i][i] = 0; B[i][i] = i; } for (int len = 1; len < n; len++) { for (int i = 0; i < n-len; i++) { int j = i + len; C[i][j] = C[i][i] + C[i+1][j] + s[i]*s[i+1]*s[j+1]; B[i][j] = i; for (int k = i+1; k < j; k++) { if (C[i][k] + C[k+1][j] + s[i]*s[k+1]*s[j+1] < C[i][j]) { C[i][j] = C[i][k] + C[k+1][j] + s[i]*s[k+1]*s[j+1]; B[i][j] = k; } } } }