Find the maximum number of composite summands of a number | PHP implementation of the above approach ; Function to generate the dp array ; combination of three integers ; take the maximum number of summands ; Function to find the maximum number of summands ; If n is a smaller number , less than 16 return dp [ n ] ; Else , find a minimal number t as explained in solution ; Driver code ; Generate dp array
< ? php $ maxn = 16 ; function precompute ( ) { $ dp = array_fill ( 0 , $ GLOBALS [ ' axn ' , -1 ) ; $ dp [ 0 ] = 0 ; $ v = array ( 4 , 6 , 9 ) ; for ( $ i = 1 ; $ i < $ GLOBALS [ ' axn ' ; ++ $ i ) { for ( $ k = 0 ; $ k < 3 ; $ k ++ ) { $ j = $ v [ $ k ] ; if ( $ i >= $ j && $ dp [ $ i - $ j ] != -1 ) { $ dp [ $ i ] = max ( $ dp [ $ i ] , $ dp [ $ i - $ j ] + 1 ) ; } } } return $ dp ; } function Maximum_Summands ( $ dp , $ n ) { if ( $ n < $ GLOBALS [ ' axn ' ) return $ dp [ $ n ] ; else { $ t = ( $ n - $ GLOBALS [ ' axn ' ) / 4 + 1 ; return $ t + $ dp [ $ n - 4 * $ t ] ; } } $ n = 12 ; $ dp = precompute ( ) ; echo Maximum_Summands ( $ dp , $ n ) ; ? >