PHP-Fusion Powered Website - Articles: C++ Program to Perform Optimal Parenthesize using Dynamic Programming

Users Online

· Guests Online: 115

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Perform Optimal Parenthesize using Dynamic Programming

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

C++ Program to Perform Optimal Parenthesize using Dynamic Programming

C++ Program to Perform Optimal Parenthesize using Dynamic Programming

Comments

Post Comment

Ratings