Recursively break a number in 3 parts to get maximum sum | Function to find the maximum sum ; base conditions ; Fill in bottom - up manner using recursive formula . ; Driver Code
< ? php function breakSum ( $ n ) { $ dp = array_fill ( 0 , $ n + 1 , 0 ) ; $ dp [ 0 ] = 0 ; $ dp [ 1 ] = 1 ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) $ dp [ $ i ] = max ( $ dp [ ( int ) ( $ i / 2 ) ] + $ dp [ ( int ) ( $ i / 3 ) ] + $ dp [ ( int ) ( $ i / 4 ) ] , $ i ) ; return $ dp [ $ n ] ; } $ n = 24 ; echo breakSum ( $ n ) ; ? >