Question

Recall the Matrix Chain Multiplication Algorithm for determining the optimal parenthesization for a product of matrices. Provide a recursive implementation of the function

void print_parenth(Matrix K[], int i, int j);

that takes as input the matrix K of k values that are needed to construct the optimal parenthesization for Ai · · · Aj . Assume access to a print function that takes as input a string and prints its value. You may also assume a “+” operation for string concatenation, and that integers are automatically converted to strings. Finally, assume that a single matrix does not require a set of outer parentheses, but two or more matrices do. For example, to print ((A1A2)A3), one could write

print "((A" + 1 + "A" + 2 + ")A" + 3 + ")"

Answer 1

Here am providing the full code of matrix chain multiplication. Hope this helps you. Please give an upvote. Thank you.

#include <bits/stdc++.h>
using namespace std;

// Matrix Ai has dimension p[i-1] x p[i]
// for i = 1..n
int MatrixChainOrder(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 = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];

if (count < min)
min = count;
}

// Return minimum count
return min;
}

// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, n - 1);
}