Matrix Chain Multiplication ( A O ( N ^ 2 ) Solution ) | Matrix Mi 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 dp [ ] [ ] . 0 th row and 0 th column of dp [ ] [ ] are not used ; cost is zero when multiplying one matrix . ; Simply following above recursive formula . ; Driver code
function MatrixChainOrder ( p , n ) { var dp = Array . from ( Array ( n ) , ( ) => Array ( n ) ) ; for ( var i = 1 ; i < n ; i ++ ) dp [ i ] [ i ] = 0 ; for ( var L = 1 ; L < n - 1 ; L ++ ) for ( var i = 1 ; i < n - L ; i ++ ) dp [ i ] [ i + L ] = Math . min ( dp [ i + 1 ] [ i + L ] + p [ i - 1 ] * p [ i ] * p [ i + L ] , dp [ i ] [ i + L - 1 ] + p [ i - 1 ] * p [ i + L - 1 ] * p [ i + L ] ) ; return dp [ 1 ] [ n - 1 ] ; } var arr = [ 10 , 20 , 30 , 40 , 30 ] ; var size = arr . length ; document . write ( " " + MatrixChainOrder ( arr , size ) ) ;