Question

READ CAREFULLY AND CODE IN C++

Dynamic Programming: Matrix Chain Multiplication Description In this assignment you are asked to implement a dynamic programming algorithm: matrix chain multiplication (chapter 15.2), where the goal is to find the most computationally efficient matrix order when multiplying an arbitrary number of matrices in a row. You can assume that the entire input will be given as integers that can be stored using the standard C++ int type and that matrix sizes will be at least 1. Input The input has the following format. The first number, n ≥ 1, in the test case will tell you how many matrices are in the sequence. The first number will be then followed by n + 1 numbers indicating the size of the dimensions of the matrices. Recall that the given information is enough to fully specify the dimensions of the matrices to be multiplied. Output First, you need to output the minimum number of scalar multiplications needed to multiply the given matrices. Then, print the matrix multiplication sequence, via parentheses, that minimizes the total number of number multiplications and the . for multiplication symbol. Each matrix should be named A#, where # is the matrix number starting at 0 (zero) and ending at n − 1. See the examples below. Examples of input and output 2 2 3 5 30 (A0.A1) 3 10 100 5 50 7500 ((A0.A1).A2) 3 10 30 5 60 4500 ((A0.A1).A2) 6 30 35 15 5 10 20 25 15125 ((A0.(A1.A2)).((A3.A4).A5))

READ CAREFULLY AND CODE IN C++

Dynamic Programming: Matrix Chain Multiplication Description In this assignment you are asked to implement a dynamic programming algo- rithm: matrix chain multiplication (chapter 15.2), where the goal is to find the most computa- tionally efficient matrix order when multiplying an arbitrary number of matrices in a row. You can assume that the entire input will be given as integers that can be stored using the standard C++ int type and that matrix sizes wll be at least 1 Input The input has the following format. The first number, n 21, in the test case will tell you how many matrices are in the sequence. The first number w be then followed by n+1 numbers indicating the size of the dimensions of the matrices. R that the given information is enough to fully specify the dimensions of the matrices to be multiplied. Output First, you need to output the minimum number of scalar multiplications needed to multiply the given matrices. Then, print the matrix multiplication sequence, via parentheses, that minimizes the total number of number multiplications and the for multiplication symbol. Each matrix should be named A#, where # is the matrix number starting at 0 (zero) and ending at n - 1. See the examples below Examples of input and output 2 35 30 CAO.A1) 10 100 5 50 7500 ((A0.A1).A2) 10 30 5 60 4500 ((A0.A1).A2) 30 35 15 5 10 20 25 15125

READ CAREFULLY AND CODE IN C++

Answer 1

If you have any doubts, please give me comment...

#include <iostream>

#include <climits>

using namespace std;

void printParenthesis(int i, int j, int n, int *brac, int &name)

{

    if (i == j)

    {

        cout << "A" << name++;

        return;

    }

    cout << "(";

    printParenthesis(i, *((brac + i * n) + j), n, brac, name);

cout<<".";

    printParenthesis(*((brac + i * n) + j) + 1, j, n, brac, name);

cout << ")";

}

void matrixChainOrder(int arr[], int n)

{

    int arr1[n][n];

    int brac[n][n];

    for (int i = 1; i < n; i++)

        arr1[i][i] = 0;

    for (int L = 2; L < n; L++)

    {

        for (int i = 1; i < n - L + 1; i++)

        {

            int j = i + L - 1;

            arr1[i][j] = INT_MAX;

            for (int k = i; k <= j - 1; k++)

            {

                int q = arr1[i][k] + arr1[k + 1][j] + arr[i - 1] * arr[k] * arr[j];

                if (q < arr1[i][j])

                {

                    arr1[i][j] = q;

                    brac[i][j] = k;

                }

            }

        }

    }

    int name = 0;

    cout << arr1[1][n - 1] << endl;

    printParenthesis(1, n - 1, n, (int *)brac, name);

    cout << endl;

}

int main()

{

    int n, i;

    cin >> n;

    int *arr = new int[n + 1];

    for (i = 0; i <= n; i++)

    {

        cin >> arr[i];

    }

    matrixChainOrder(arr, n + 1);

    return 0;

}