Question

there are n farms in a row, at each farm you either i) collect apples or ii) drink milk(energy). visiting each farm costs you one unit of energy. this means if energy becomes zero, you cannot visit anymore farms. given initial energy (even before first farm is visited) as p, find the maximum number of apples which we can collect.

Answer 1

How do I solve the problem of collecting apples using

Answer

Let us define 2 dimensional dp,

int dp[n+1][n+1]dp[n+1][n+1]

Where dp[i][j]dp[i][j] represent no. of apple when you are at ithith farm and your energy is jj unit.

So,If we take apple from ithith farm,

dp[i][j-1] = max(dp[i][j-1],, dp[i-1][j]+apple[i]) where 11≤j≤n.≤j≤n.

if we take milk from ithith farm,

dp[i][min(j+mil[i]-1,n)] = max(dp[i][min(j+mil[i]-1,n)],dp[i-1][j]). 1≤j≤n.1≤j≤n.

Note: If energy is more than n then we can simply take it n because in n unit energy we can visit all farm.

when energy is zero, we can’t go further therefor we simply add this

dp[i][0] = max(dp[i][0],dp[i-1][0])

Base case:

Replace all element in the table with -1.

Initially we have energy p and 0 apple so dp[0][min(p,n)] = 0. if p≥np≥n then take it n as explain above.

Our answer is max of dp[n][j] 0≤j≤n.0≤j≤n.

Here is my java code,