Minimum sum of multiplications of n numbers | Used in recursive memoized solution ; function to calculate the cumulative sum from a [ i ] to a [ j ] ; base case ; memoization , if the partition has been called before then return the stored value ; store a max value ; we break them into k partitions ; store the min of the formula thus obtained ; return the minimum ; Driver code
< ? php $ dp = array ( array ( ) ) ; function sum ( $ a , $ i , $ j ) { $ ans = 0 ; for ( $ m = $ i ; $ m <= $ j ; $ m ++ ) $ ans = ( $ ans + $ a [ $ m ] ) % 100 ; return $ ans ; } function solve ( $ a , $ i , $ j ) { global $ dp ; if ( $ i == $ j ) return 0 ; if ( $ dp [ $ i ] [ $ j ] != -1 ) return $ dp [ $ i ] [ $ j ] ; $ dp [ $ i ] [ $ j ] = PHP_INT_MAX ; for ( $ k = $ i ; $ k < $ j ; $ k ++ ) { $ dp [ $ i ] [ $ j ] = min ( $ dp [ $ i ] [ $ j ] , ( solve ( $ a , $ i , $ k ) + solve ( $ a , $ k + 1 , $ j ) + ( sum ( $ a , $ i , $ k ) * sum ( $ a , $ k + 1 , $ j ) ) ) ) ; } return $ dp [ $ i ] [ $ j ] ; } function initialize ( $ n ) { global $ dp ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) $ dp [ $ i ] [ $ j ] = -1 ; } $ a = array ( 40 , 60 , 20 ) ; $ n = count ( $ a ) ; initialize ( $ n ) ; echo solve ( $ a , 0 , $ n - 1 ) ; ? >