//
//  main.cpp
//  Matrix Chain Multiplication
//
//  Created by Himanshu on 17/09/21.
//

#include <iostream>
#include <climits>
using namespace std;
const int N = 5;

void MatrixChainMultiplication (int p[]) {
 
    int M[N][N];
    for (int i=0; i<N; i++) { 
        for (int j=0; j<N; j++) {
            if (i == j) {
                M[i][j] = 0;
            } else {
                M[i][j] = INT_MAX;
            }
        }
    }

    // c is the length of chained matrices
    for (int c=2; c<N; c++) {
        for (int i=1; i<(N-c+1); i++) {
            int j = i+c-1;
            for (int k=i; k<j; k++) {
                M[i][j] = min(M[i][j], (M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j]));
            }
        }
    }
    
    cout<<M[1][N-1]<<endl;
    
}
 
int main() {
    //For matrices M1(5x4), M2(4x6), M3(6x2), M4(2x7)
    int A[] = {5, 4, 6, 2, 7};
    MatrixChainMultiplication(A);
}