Camel and Banana Puzzle | DP | Stores the overlapping state ; Recursive function to find the maximum number of bananas that can be transferred to A distance using memoization ; Base Case where count of bananas is less that the given distance ; Base Case where count of bananas is less that camel 's capacity ; Base Case where distance = 0 ; If the current state is already calculated ; Stores the maximum count of bananas ; Stores the number of trips to transfer B bananas using a camel of capacity C ; Loop to iterate over all the breakpoints in range [ 1 , A ] ; Recursive call over the remaining path ; Update the maxCount ; Memoize the current value ; Return answer ; Function to find the maximum number of bananas that can be transferred ; Function Call ; Driver Code
dp = [ [ - 1 for i in range ( 3001 ) ] for j in range ( 1001 ) ] NEW_LINE def recBananaCnt ( A , B , C ) : NEW_LINE INDENT if ( B <= A ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( B <= C ) : NEW_LINE INDENT return B - A NEW_LINE DEDENT if ( A == 0 ) : NEW_LINE INDENT return B NEW_LINE DEDENT if ( dp [ A ] [ B ] != - 1 ) : NEW_LINE INDENT return dp [ A ] [ B ] NEW_LINE DEDENT maxCount = - 2 ** 32 NEW_LINE tripCount = ( ( 2 * B ) // C ) - 1 if ( B % C == 0 ) else ( ( 2 * B ) // C ) + 1 NEW_LINE for i in range ( 1 , A + 1 ) : NEW_LINE INDENT curCount = recBananaCnt ( A - i , B - tripCount * i , C ) NEW_LINE if ( curCount > maxCount ) : NEW_LINE INDENT maxCount = curCount NEW_LINE dp [ A ] [ B ] = maxCount NEW_LINE DEDENT DEDENT return maxCount NEW_LINE DEDENT def maxBananaCnt ( A , B , C ) : NEW_LINE INDENT return recBananaCnt ( A , B , C ) NEW_LINE DEDENT A = 1000 NEW_LINE B = 3000 NEW_LINE C = 1000 NEW_LINE print ( maxBananaCnt ( A , B , C ) ) NEW_LINE