Camel and Banana Puzzle | DP | Stores the overlapping state Initialize dp array with - 1 ; 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
let dp = new Array ( 1001 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = ( new Array ( 3001 ) . fill ( - 1 ) ) } function recBananaCnt ( A , B , 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 ] ; } let maxCount = Number . MIN_VALUE ; let tripCount = B % C == 0 ? Math . floor ( ( 2 * B ) / C ) - 1 : Math . floor ( ( 2 * B ) / C ) + 1 ; for ( let i = 1 ; i <= A ; i ++ ) { let curCount = recBananaCnt ( A - i , B - tripCount * i , C ) ; if ( curCount > maxCount ) { maxCount = curCount ; dp [ A ] [ B ] = maxCount ; } } return maxCount ; } function maxBananaCnt ( A , B , C ) { return recBananaCnt ( A , B , C ) ; } let A = 1000 ; let B = 3000 ; let C = 1000 ; document . write ( maxBananaCnt ( A , B , C ) ) ;