//
// 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);
}
Ly8KLy8gIG1haW4uY3BwCi8vICBNYXRyaXggQ2hhaW4gTXVsdGlwbGljYXRpb24KLy8KLy8gIENyZWF0ZWQgYnkgSGltYW5zaHUgb24gMTcvMDkvMjEuCi8vCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjbGltaXRzPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpjb25zdCBpbnQgTiA9IDU7Cgp2b2lkIE1hdHJpeENoYWluTXVsdGlwbGljYXRpb24gKGludCBwW10pIHsKIAogICAgaW50IE1bTl1bTl07CiAgICBmb3IgKGludCBpPTA7IGk8TjsgaSsrKSB7IAogICAgICAgIGZvciAoaW50IGo9MDsgajxOOyBqKyspIHsKICAgICAgICAgICAgaWYgKGkgPT0gaikgewogICAgICAgICAgICAgICAgTVtpXVtqXSA9IDA7CiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICBNW2ldW2pdID0gSU5UX01BWDsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICAvLyBjIGlzIHRoZSBsZW5ndGggb2YgY2hhaW5lZCBtYXRyaWNlcwogICAgZm9yIChpbnQgYz0yOyBjPE47IGMrKykgewogICAgICAgIGZvciAoaW50IGk9MTsgaTwoTi1jKzEpOyBpKyspIHsKICAgICAgICAgICAgaW50IGogPSBpK2MtMTsKICAgICAgICAgICAgZm9yIChpbnQgaz1pOyBrPGo7IGsrKykgewogICAgICAgICAgICAgICAgTVtpXVtqXSA9IG1pbihNW2ldW2pdLCAoTVtpXVtrXSArIE1baysxXVtqXSArIHBbaS0xXSpwW2tdKnBbal0pKTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIAogICAgY291dDw8TVsxXVtOLTFdPDxlbmRsOwogICAgCn0KIAppbnQgbWFpbigpIHsKICAgIC8vRm9yIG1hdHJpY2VzIE0xKDV4NCksIE0yKDR4NiksIE0zKDZ4MiksIE00KDJ4NykKICAgIGludCBBW10gPSB7NSwgNCwgNiwgMiwgN307CiAgICBNYXRyaXhDaGFpbk11bHRpcGxpY2F0aW9uKEEpOwp9Cgo=