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
< ? php function MatrixChainOrder ( $ p , $ n ) { $ dp = array ( ) ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ dp [ $ i ] [ $ i ] = 0 ; for ( $ L = 1 ; $ L < $ n - 1 ; $ L ++ ) for ( $ i = 1 ; $ i < $ n - $ L ; $ i ++ ) $ dp [ $ i ] [ $ i + $ L ] = 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 ] ; } $ arr = array ( 10 , 20 , 30 , 40 , 30 ) ; $ size = sizeof ( $ arr ) ; echo " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " . MatrixChainOrder ( $ arr , $ size ) ; ? >