text: Matrix Chain Multiplication | DP | A naive recursive implementation that simply follows the above optimal substructure property ; Matrix Ai has dimension p [ i - 1 ] x p [ i ] for i = 1. . n ; place parenthesis at different places between first and last matrix , recursively calculate count of multiplications for each parenthesis placement and return the minimum count ; Return minimum count ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int MatrixChainOrder ( int p [ ] , int i , int j ) { if ( i == j ) return 0 ; int k ; int min = INT_MAX ; int 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 min ; } 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 ) ; }