10/25/2018 - 2:58 PM

Matrix Chain Multiplication

#include <iostream>
using namespace std;

int main() {
    int n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>> a[i];

    int dp[n][n];//stores cost of multiplying ith matrix through jth matrix (both inclusive)
    for (int i=0;i<n;i++)//when there is only one matrix, the cost is zero
        dp[i][i]= 0;

    for (int length= 2;length<n;length++) {
        for (int i=1;i<=n-length;i++) {//start from ith matrix and increase the no.of matrices
            int j= i+length-1;

            dp[i][j]= INT_MAX;
            for (int k=i; k<j;k++)//if kth matrix is the last one that remains to be multiplied
                dp[i][j]= min(dp[i][j],dp[i][k]+dp[k+1][j] +a[i-1]*a[k]*a[j]);
    cout<< dp[1][n-1];