C Program to Perform Optimal Parenthesize using Dynamic Programming

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 Books in C Programming, Data Structures and Algorithms.

« Prev - C Program to Implement Sieve of Atkin to Generate Prime Numbers

» Next - C Program to Implement Stooge Sort Algorithm

Related Posts:

Recommended Articles: