Matrix Multiplication

This problem gives a string of multiple matrix multiplications and supposes that there is a cost for each intermediate matrix during the sequence of multiplications. We are asked to perform the multiplications in such an order that minimizes the intermediate storage.

This is a standard partitioning dynamic programming problem.

DP[i][j]=minimum cost to multiply from matrices i to j

For each element, the relation is

dp[i][j] = min of i<k<j: dp[i][k-1] + dp[k][j] + cost((k-1)*k)

The DP array is n^2 large, and the relation takes n time, but we find that only n^2/2 entries are actually valid, and somewhere aorund n^2/6, or precisely 166666500. this should be fast enough. .