// See the Cormen book for details of the following algorithm
#include<stdio.h>
#include<limits.h>
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra row and one extra column are
allocated in m[][]. 0th row and 0th column of m[][] are not used */
int m[n][n];
int i, j, k, L, q;
/* m[i,j] = Minimum number of scalar multiplications needed to compute
the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L=2; L<n; L++)
{
for (i=1; i<=n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n-1];
}
int main()
{
int arr[] = {1, 2, 3, 4};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ", MatrixChainOrder(arr, size));
return 0;
}
Ly8gU2VlIHRoZSBDb3JtZW4gYm9vayBmb3IgZGV0YWlscyBvZiB0aGUgZm9sbG93aW5nIGFsZ29yaXRobQojaW5jbHVkZTxzdGRpby5oPgojaW5jbHVkZTxsaW1pdHMuaD4KCi8vIE1hdHJpeCBBaSBoYXMgZGltZW5zaW9uIHBbaS0xXSB4IHBbaV0gZm9yIGkgPSAxLi5uCmludCBNYXRyaXhDaGFpbk9yZGVyKGludCBwW10sIGludCBuKQp7CgogICAgLyogRm9yIHNpbXBsaWNpdHkgb2YgdGhlIHByb2dyYW0sIG9uZSBleHRyYSByb3cgYW5kIG9uZSBleHRyYSBjb2x1bW4gYXJlCiAgICAgICBhbGxvY2F0ZWQgaW4gbVtdW10uICAwdGggcm93IGFuZCAwdGggY29sdW1uIG9mIG1bXVtdIGFyZSBub3QgdXNlZCAqLwogICAgaW50IG1bbl1bbl07CgogICAgaW50IGksIGosIGssIEwsIHE7CgogICAgLyogbVtpLGpdID0gTWluaW11bSBudW1iZXIgb2Ygc2NhbGFyIG11bHRpcGxpY2F0aW9ucyBuZWVkZWQgdG8gY29tcHV0ZQogICAgICAgdGhlIG1hdHJpeCBBW2ldQVtpKzFdLi4uQVtqXSA9IEFbaS4ual0gd2hlcmUgZGltZW50aW9uIG9mIEFbaV0gaXMKICAgICAgIHBbaS0xXSB4IHBbaV0gKi8KCiAgICAvLyBjb3N0IGlzIHplcm8gd2hlbiBtdWx0aXBseWluZyBvbmUgbWF0cml4LgogICAgZm9yIChpID0gMTsgaSA8IG47IGkrKykKICAgICAgICBtW2ldW2ldID0gMDsKCiAgICAvLyBMIGlzIGNoYWluIGxlbmd0aC4gIAogICAgZm9yIChMPTI7IEw8bjsgTCsrKSAgIAogICAgewogICAgICAgIGZvciAoaT0xOyBpPD1uLUwrMTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgaiA9IGkrTC0xOwogICAgICAgICAgICBtW2ldW2pdID0gSU5UX01BWDsKICAgICAgICAgICAgZm9yIChrPWk7IGs8PWotMTsgaysrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvLyBxID0gY29zdC9zY2FsYXIgbXVsdGlwbGljYXRpb25zCiAgICAgICAgICAgICAgICBxID0gbVtpXVtrXSArIG1baysxXVtqXSArIHBbaS0xXSpwW2tdKnBbal07CiAgICAgICAgICAgICAgICBpZiAocSA8IG1baV1bal0pCiAgICAgICAgICAgICAgICAgICAgbVtpXVtqXSA9IHE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIG1bMV1bbi0xXTsKfQoKaW50IG1haW4oKQp7CiAgICBpbnQgYXJyW10gPSB7MSwgMiwgMywgNH07CiAgICBpbnQgc2l6ZSA9IHNpemVvZihhcnIpL3NpemVvZihhcnJbMF0pOwoKICAgIHByaW50ZigiTWluaW11bSBudW1iZXIgb2YgbXVsdGlwbGljYXRpb25zIGlzICVkICIsCiAgICAgICAgICAgICAgICAgICAgICAgTWF0cml4Q2hhaW5PcmRlcihhcnIsIHNpemUpKTsKCiAgICBnZXRjaGFyKCk7CiAgICByZXR1cm4gMDsKfQ==