Matrix Chain Multiplication | DP | Javascript program using memoization ; Function for matrix chain multiplication ; Driver code
let dp = new Array ( 100 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } function matrixChainMemoised ( p , i , j ) { if ( i == j ) { return 0 ; } if ( dp [ i ] [ j ] != - 1 ) { return dp [ i ] [ j ] ; } dp [ i ] [ j ] = Number . MAX_VALUE ; for ( let k = i ; k < j ; k ++ ) { dp [ i ] [ j ] = Math . min ( dp [ i ] [ j ] , matrixChainMemoised ( p , i , k ) + matrixChainMemoised ( p , k + 1 , j ) + p [ i - 1 ] * p [ k ] * p [ j ] ) ; } return dp [ i ] [ j ] ; } function MatrixChainOrder ( p , n ) { let i = 1 , j = n - 1 ; return matrixChainMemoised ( p , i , j ) ; } let arr = [ 1 , 2 , 3 , 4 ] ; let n = arr . length ; for ( var i = 0 ; i < dp . length ; i ++ ) { for ( var j = 0 ; j < dp . length ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( " " + MatrixChainOrder ( arr , n ) ) ;