C++ Program to Perform Optimal Parenthesize using Dynamic Programming
Posted by Superadmin on August 09 2022 07:01:34

C++ Program to Perform Optimal Parenthesize using Dynamic Programming

This is a C++ Program to perform optimal paranthesization using DP.

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.

```
#include<stdio.h>
```
```
#include<limits.h>
```
```
#include<iostream>
```
```
 
```
```
using namespace std;
```
```
 
```

// 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 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()
```
```
{
```
```
    cout
```

            << "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]";

```
    cout << "Enter the total length:";
```
```
    int n;
```
```
    cin >> n;
```
```
    int array[n];
```
```
    cout << "Enter the dimensions: ";
```
```
    for (int var = 0; var < n; ++var)
```
```
    {
```
```
        cin >> array[var];
```
```
    }
```

    cout << "Minimum number of multiplications is: " << MatrixChainOrder(array,

```
            n);
```
```
    return 0;
```
```
}
```

Output:

$ g++ OptimalParanthesizationDP.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