// C++ program to print optimal parenthesization // in matrix chain multiplication. #include using namespace std; // Function for printing the optimal // parenthesization of a matrix chain product void printParenthesis(int i, int j, int n, int *bracket, char &name) { // If only one matrix left in current segment if (i == j) { cout << name++; return; } cout << "("; // Recursively put brackets around subexpression // from i to bracket[i][j]. // Note that "*((bracket+i*n)+j)" is similar to // bracket[i][j] printParenthesis(i, *((bracket+i*n)+j), n, bracket, name); // Recursively put brackets around subexpression // from bracket[i][j] + 1 to j. printParenthesis(*((bracket+i*n)+j) + 1, j, n, bracket, name); cout << ")"; } // Matrix Ai has dimension p[i-1] x p[i] for i = 1..n // Please refer below article for details of this // function // https://goo.gl/k6EYKj void 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]; // bracket[i][j] stores optimal break point in // subexpression from i to j. int bracket[n][n]; /* 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 (int i=1; i