This is a C Program to perform optimal paranthesization using DP. This program determines the order in which the chain of matrices should be multiplied.

Here is source code of the C Program to Perform Optimal Paranthesization Using Dynamic Programming. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/* A naive recursive implementation that simply follows the above optimal`

`substructure property */`

`#include<stdio.h>`

`#include<limits.h>`

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 s[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;

s[i][j] = k;

`}`

`}`

`}`

`}`

return m[1][n - 1];

`}`

int main() {

printf(

"Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]");

printf("Enter the total length:");

int n;

scanf("%d", &n);

int array[n];

printf("Enter the dimensions: ");

int var;

for (var = 0; var < n; ++var) {

scanf("%d", array[var]);

`}`

printf("Minimum number of multiplications is: %d",

MatrixChainOrder(array, n));

return 0;

`}`

Output:

$ gcc OptimalParanthesization.cpp $ ./a.out Enter the array p[], which represents the chain of matrices such that the ith matrix Ai is of dimension p[i-1] x p[i]Enter the total length:4 Enter the dimensions: 2 4 3 5 Minimum number of multiplications is: 54

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Reference Books in C Programming, Data Structures and Algorithms.