Matrix Chain Multiplication | DP | 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
< ? php function MatrixChainOrder ( $ p , $ n ) { $ m [ ] [ ] = array ( $ n , $ n ) ; 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 ] = PHP_INT_MAX ; 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 ] ; } $ arr = array ( 1 , 2 , 3 , 4 ) ; $ size = sizeof ( $ arr ) ; echo " Minimum ▁ number ▁ of ▁ multiplications ▁ is ▁ " . MatrixChainOrder ( $ arr , $ size ) ; ? >