Farida - Princess Farida

Hi, Everyone
I am struggling in this question from morning. I know there are many solutions out there, but I tried to use my own logic.

I tried every approach with Recursion, Dp but still i got wrong answer. I want someone to please help me with logic.

Recursion- Bottom Up Approach

private static long maximumMonsterMoney(long[] arr, int i) {
if (i >= arr.length) {
return 0;
}
long take = arr[i] + maximumMonsterMoney(arr, i + 2);
long leave = maximumMonsterMoney(arr, i + 1);
return Math.max(take, leave);
}

Top Down Approach

private static void maximumMonsterSum(long[] arr, int start, long sum) {
if (start >= arr.length) {
set.add(sum);
return;
}
sum = sum + arr[start];
maximumMonsterSum(arr, start + 2, sum);
sum = sum - arr[start];
maximumMonsterSum(arr, start + 1, sum);
return;
}

DP- Memoization

private static long maximumMonsterMoneyUsingMemo(long[] arr, int i) {
if (i >= arr.length) {
return 0;
}
if (hm.containsKey(i)) {
return hm.get(i);
}
long take = arr[i] + maximumMonsterMoney(arr, i + 2);
long leave = maximumMonsterMoney(arr, i + 1);
hm.put(i, Math.max(take, leave));
return hm.get(i);
}

DP- Tabulation. I am not being able to solve it.

If there is any issue in this logic please help

I don’t want to cramp those google answers.

Thanks in advance

It is not necessary that you have to take the coins in alternate positions. That is, if you are at position i, you can either take coins from position (i-2) or (i-3). If I’m not wrong, you are considering only the (i-2) case.

I am considering that
if I take current coin then i cannot take adjacent coin
and
If i cannot take current coin then i will take adjacent coin.

and this is where my logic applies

Take current coin or not take current coin.

What I mean is, you can also leave two in a row. For example, in the recursion-bottom up approach, instead of
long take = arr[i] + maximumMonsterMoney(arr, i+2);
it should be
long take = arr[i] + Math.max(maximumMonsterMoney(arr, i+2), maximumMonsterMoney(arr, i+3));
Because in the previous one, there is no way in which the ith element and (i+3)th element can come together. :sweat_smile:

@kan_pard_005

Soory for such bad drawing but i think this can give the idea of what am i thinking.

i+3 is included as (1, 4) in below circles.

Please continue the discussion. As i want to know where am i lacking.

oops i lacked one right side. Please that’s just a cross over there. But have a look at it.

dp[i]=max(dp[i-1],dp[i-2]+a[i]);

@abhay_2012

Hi, Thanks for answer but i want to know is it necessary that i have to always look backward i-1 and i-2, why can i not be able to use i+1 and i+2 with bottom up DP.

Here’s an iterative variant of the code in C++ (I’m really sorry, I’m not that conversant in Java):

long long int arr[n+3], sum[n+3];
for (int i=3; i<n+3; i++) {
cin>>arr[i];
}
sum[0] = sum[1] = sum[2] = 0;
for (int i=3; i<n+3; i++) sum[i] = arr[i] + max(sum[i-2], sum[i-3]);

I like to think of it as dividing the array into two parts: an ‘explored’ part and an ‘unexplored’ part. After each iteration (or each function call, in the case of recursion), we add another element from the ‘explored’ part to the ‘unexplored’ part. As long as this explored-unexlpored division is correct, it works fine!
In recursion, we ensure that we do explore the supposedly explored side in the necessary way to get the answer.

From your diagram, it’s clear that you have the right idea! The catch is in the implementation. If you run through one of the codes you’ve written (let’s say the recursion-bottom up approach), then you will see that 1 and 4 are never physically added. take contains 1 and 3, while leave contains 2 and further numbers.
There’s another way to think of the problem: Let’s say we are at position i. Going ahead, we can choose either i+1, i+2, i+3, i+4…positions as our immediately next position . But if we’re choosing i+4, we might as well choose i+2! This naturally breaks our problem into two independent sections: one in which we are choosing i+2, and another in which we are choosing i+3.

cin>>n;
FOR(i,n)cin>>a[i];
memset(dp,0,sizeof(dp));
dp[n]=0,dp[n+1]=0,dp[n+3]=0;
for(int i=n-1;i>=0;i–){
dp[i]=a[i]+max(dp[i+2],dp[i+3]);
}
ll mx=INT_MIN;
for(int i=0;i<n;i++){
mx=max(mx,dp[i]);
}

    cout<<"Case "<<p++<<": "<<mx<<"\n";

my code is showing wrong answer.Can anybody tell me why

@ojas032 It should be n+2 instead of n+3 in line 4.

1 Like

@kan_pard_005 after changing that also it is showing wrong answer

Might be the case when there are zero monsters. Initialising min to 0 might help!

2 Likes

@kan_pard_005 Thanks it worked