Camel and Banana Puzzle | DP | Java program of the above approach ; 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 ; Initialize dp array with - 1 ; Function Call ; Driver Code
public class GFG { final static int dp [ ] [ ] = new int [ 1001 ] [ 3001 ] ; static int recBananaCnt ( int A , int B , int C ) { if ( B <= A ) { return 0 ; } if ( B <= C ) { return B - A ; } if ( A == 0 ) { return B ; } if ( dp [ A ] [ B ] != - 1 ) { return dp [ A ] [ B ] ; } int maxCount = Integer . MIN_VALUE ; int tripCount = B % C == 0 ? ( ( 2 * B ) / C ) - 1 : ( ( 2 * B ) / C ) + 1 ; for ( int i = 1 ; i <= A ; i ++ ) { int curCount = recBananaCnt ( A - i , B - tripCount * i , C ) ; if ( curCount > maxCount ) { maxCount = curCount ; dp [ A ] [ B ] = maxCount ; } } return maxCount ; } static int maxBananaCnt ( int A , int B , int C ) { for ( int i = 0 ; i < 1001 ; i ++ ) for ( int j = 0 ; j < 3001 ; j ++ ) dp [ i ] [ j ] = - 1 ; return recBananaCnt ( A , B , C ) ; } public static void main ( String [ ] args ) { int A = 1000 ; int B = 3000 ; int C = 1000 ; System . out . println ( maxBananaCnt ( A , B , C ) ) ; } }