Printing brackets in Matrix Chain Multiplication Problem | C ++ program to print optimal parenthesization in matrix chain multiplication . ; Function for printing the optimal parenthesization of a matrix chain product ; If only one matrix left in current segment ; Recursively put brackets around subexpression from i to bracket [ i ] [ j ] . Note that " * ( ( bracket + i * n ) + j ) " is similar to bracket [ i ] [ j ] ; Recursively put brackets around subexpression from bracket [ i ] [ j ] + 1 to j . ; 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 ; For simplicity of the program , one extra row and one extra column are allocated in m [ ] [ ] . 0 th row and 0 th column of m [ ] [ ] are not used ; bracket [ i ] [ j ] stores optimal break point in subexpression from i to j . ; cost is zero when multiplying one matrix . ; L is chain length . ; q = cost / scalar multiplications ; Each entry bracket [ i , j ] = k shows where to split the product arr i , i + 1. . . . j for the minimum cost . ; The first matrix is printed as ' A ' , next as ' B ' , and so on ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printParenthesis ( int i , int j , int n , int * bracket , char & name ) { if ( i == j ) { cout << name ++ ; return ; } cout << " ( " ; printParenthesis ( i , * ( ( bracket + i * n ) + j ) , n , bracket , name ) ; printParenthesis ( * ( ( bracket + i * n ) + j ) + 1 , j , n , bracket , name ) ; cout << " ) " ; } void matrixChainOrder ( int p [ ] , int n ) { int m [ n ] [ n ] ; int bracket [ n ] [ n ] ; for ( int i = 1 ; i < n ; i ++ ) m [ i ] [ i ] = 0 ; for ( int L = 2 ; L < n ; L ++ ) { for ( int i = 1 ; i < n - L + 1 ; i ++ ) { int j = i + L - 1 ; m [ i ] [ j ] = INT_MAX ; for ( int k = i ; k <= j - 1 ; k ++ ) { int q = m [ i ] [ k ] + m [ k + 1 ] [ j ] + p [ i - 1 ] * p [ k ] * p [ j ] ; if ( q < m [ i ] [ j ] ) { m [ i ] [ j ] = q ; bracket [ i ] [ j ] = k ; } } } } char name = ' A ' ; cout << " Optimal ▁ Parenthesization ▁ is ▁ : ▁ " ; printParenthesis ( 1 , n - 1 , n , ( int * ) bracket , name ) ; cout << " nOptimal ▁ Cost ▁ is ▁ : ▁ " << m [ 1 ] [ n - 1 ] ; } int main ( ) { int arr [ ] = { 40 , 20 , 30 , 10 , 30 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; matrixChainOrder ( arr , n ) ; return 0 ; }