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);
}
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.
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.
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.
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.
