Given a chain of matrices, Matrix Chain Multiplication finds the order of multiplication that minimizes the total number of scalar operations. The number of ways to parenthesize grows exponentially, but DP solves it in O(n³) by building up solutions for chains of increasing length.
int matrixChain(vector<int>& dims) {
int n=dims.size()-1;
vector<vector<int>> dp(n,vector<int>(n,0));
for(int len=2;len<=n;len++)
for(int i=0;i<=n-len;i++) {
int j=i+len-1;
dp[i][j]=INT_MAX;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+dims[i]*dims[k+1]*dims[j+1]);
}
return dp[0][n-1];
}Multiplying matrices A(10x30) * B(30x5) * C(5x60): doing (AB)C costs 10*30*5 + 10*5*60 = 4500. Doing A(BC) costs 30*5*60 + 10*30*60 = 27000. Order dramatically changes cost.
dp[i][j] = minimum cost to multiply matrices i through j. Split at every k between i and j: cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]. Take the minimum over all k.
Fill dp by increasing chain length. Length-1 chains cost 0 (single matrix). Length-2, then 3, etc. Each longer chain uses already-computed shorter chain costs.
Quiz coming soon for this algorithm.