Find the maximum number of composite summands of a number | Python 3 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
global maxn NEW_LINE maxn = 16 NEW_LINE def precompute ( ) : NEW_LINE INDENT dp = [ - 1 for i in range ( maxn ) ] NEW_LINE dp [ 0 ] = 0 NEW_LINE v = [ 4 , 6 , 9 ] NEW_LINE for i in range ( 1 , maxn , 1 ) : NEW_LINE INDENT for k in range ( 3 ) : NEW_LINE INDENT j = v [ k ] NEW_LINE if ( i >= j and dp [ i - j ] != - 1 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , dp [ i - j ] + 1 ) NEW_LINE DEDENT DEDENT DEDENT return dp NEW_LINE DEDENT def Maximum_Summands ( dp , n ) : NEW_LINE INDENT if ( n < maxn ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT else : NEW_LINE INDENT t = int ( ( n - maxn ) / 4 ) + 1 NEW_LINE return t + dp [ n - 4 * t ] NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 12 NEW_LINE dp = precompute ( ) NEW_LINE print ( Maximum_Summands ( dp , n ) ) NEW_LINE DEDENT