Matrix Chain Multiplication | DP | Matrix Chain Multiplication . See the Cormen book for details of the following algorithm Matrix Ai has dimension p [ i - 1 ] x p [ i ] for i = 1. . n ; 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 ; cost is zero when multiplying one matrix . ; L is chain length . ; q = cost / scalar multiplications ; Driver code
function MatrixChainOrder ( p , n ) { var m = Array ( n ) . fill ( 0 ) . map ( x => Array ( n ) . fill ( 0 ) ) ; var i , j , k , L , q ; for ( i = 1 ; i < n ; i ++ ) m [ i ] [ i ] = 0 ; for ( L = 2 ; L < n ; L ++ ) { for ( i = 1 ; i < n - L + 1 ; i ++ ) { j = i + L - 1 ; if ( j == n ) continue ; m [ i ] [ j ] = Number . MAX_VALUE ; for ( k = i ; k <= j - 1 ; k ++ ) { q = m [ i ] [ k ] + m [ k + 1 ] [ j ] + p [ i - 1 ] * p [ k ] * p [ j ] ; if ( q < m [ i ] [ j ] ) m [ i ] [ j ] = q ; } } } return m [ 1 ] [ n - 1 ] ; } var arr = [ 1 , 2 , 3 , 4 ] ; var size = arr . length ; document . write ( " " + MatrixChainOrder ( arr , size ) ) ;