Import necessary libraries and namespaces
#include<stdio.h>
#include<limits.h>
#include<iostream>
using namespace std;
Recursive function to calculate nth Catalan number
// A recursive function to find nth catalan number
int catalan(int n)
{
// Base case
if (n <= 1) return 1;
// catalan(n) is sum of catalan(i)*catalan(n-i-1)
int res = 0;
for (int i=0; i<n; i++)
res += catalan(i)*catalan(n-i-1);
return res;
}
Implementation of dynamic approach recursively
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrderRecursive(int p[], int i, int j)
{
if(i == j)
return 0;
int k;
int min = INT_MAX;
int count;
/* place parenthesis at different places
between first and last matrix, recursively
calculate count of multiplications for
each parenthesis placement and return the
minimum count */
for (k = i; k < j; k++)
{
count = MatrixChainOrderRecursive(p, i, k)
+ MatrixChainOrderRecursive(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];
if (count < min)
min = count;
}
// Return minimum count
return min;
}
Implementation of bottom-up dynamic approach
// 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 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
dimension 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;
int r=i;
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;
}
}
}
}
return m[1][n-1];
}
Demonstrating the above function
int arr[] = {1, 2, 3, 4,5,6,7,8,9,10,11,12,13,14,15,16};
for(int i=2;i<=15;i++)
{
// Cost = Minimum number of multiplications needed.
cout <<"Minimum number of multiplications(dp- recursive) is " << MatrixChainOrderRecursive(arr, 1, i - 1) << "\n";
cout <<"Minimum number of multiplications(dp- bottom up) is : " << MatrixChainOrder(arr, i) << "\n";
cout << "\n";
}
Clearly, the 2 approaches don't differ widely upto small matrix size.
However, the recursive method fails to keep up for larger sizes.
To compare with the brute force method
We know from analysis of the brute force approach that it would require
exponential time corresponding to the nth Catalan number.
So, we can print out the Catalan numbers recursively for the above sizes
and contrast those values with the values for minimum number of multiplications
obtained above.
for (int i=0; i<15; i++)
cout << "Catalan number C(" << i << ") : " << catalan(i) << "\n";
Clearly, the corresponding Catalan numbers have greater numerical value.
Thus, the efficiency of the dynamic programming solution is established for matrix-chain multiplication problem.