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.
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 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[n - 1];
<< "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:";
cin >> n;
cout << "Enter the dimensions: ";
for (int var = 0; var < n; ++var)
cin >> array[var];
cout << "Minimum number of multiplications is: " << MatrixChainOrder(array,
$ 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
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Subscribe Now: C++ Algorithms Newsletter | Important Subjects Newsletters
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.
- Get Free Certificate of Merit in C++ Programming
- Participate in C++ Programming Certification Contest
- Become a Top Ranker in C++ Programming
- Take C++ Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Computer Science Books
- Apply for C++ Internship
- Apply for Information Technology Internship
- Buy Programming Books
- Apply for Computer Science Internship