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
class MatrixChainMultiplication { static int MatrixChainOrder ( int p [ ] , int i , int j ) { if ( i == j ) return 0 ; int min = Integer . MAX_VALUE ; for ( int k = i ; k < j ; k ++ ) { int count = MatrixChainOrder ( p , i , k ) + MatrixChainOrder ( p , k + 1 , j ) + p [ i - 1 ] * p [ k ] * p [ j ] ; if ( count < min ) min = count ; } return min ; } public static void main ( String args [ ] ) { int arr [ ] = new int [ ] { 1 , 2 , 3 , 4 , 3 } ; int n = arr . length ; System . out . println ( " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " + MatrixChainOrder ( arr , 1 , n - 1 ) ) ; } }