DP problem help

@vikasnitt : Does all the cells have same number of apples?

What’s the desired complexity or the time limit? Where did you get the problem from (url would be good)?

Found it on topcoder with its solution too: Topcoder

Solving one way (from top-left to bottom-right alone) is straightforward.

During this process, for each cell, store the cell from which we reached here. So, we can trace back the route we already used.

Now, trace back the route and set the number of apples in each of cells as zero (we have picked up all apples from there).

Now, again, solve using DP, in this new matrix, to obtain maximum possible apples when travelling from bottom-right to top-left.

The final answer will be the sum of phase 1 and phase 2.

2 Likes

I’m wondering, it there test case in which finding max from upper left corner to bottom left + max back is not the best solution?

And what if the problem is modified: You start on first row (wherever) and walk to last row (moves down, right/left) and then back to first row (moves up, right/left), but when you walk once to the right, you cannot move to left and vice versa…

I think Backtracking would help.

13 Likes

No, it can be different.

Thanks tijoforyou…:slight_smile:

1 Like

It was asked in my interview and i was not able to do correctly at that time…But now i have solved it correctly…

This does not work for m = n = 3 and the array 0 2 9 1 10 2 0 1 0
Your method gives 23 whereas we may collect all the 25 apples.

1 Like

@shantanuag Oh, yes! Your are right. Didn’t think that through. :frowning:

DP problem help - #4 by dtalamas24 - general - CodeChef Discuss gives a link to the problem statement and the solution. Hope this helps!

O(n^2) will be good. if u have any approach then plz share it…

Given link is of this page…

I know, this is a link that lets you reach directly at the answer. I thought, this would be faster, compared to just referring to the solution.

Of course there are such cases. One of them is mentioned in one of the comments.

1 Like

I missed that one, thanks :wink:

Yes, there are some cases in which finding max from upper left corner to bottom right plus max back from bottom right to upper left is not the optimal solution. Can we do it through finding all the paths from upper to down + down to upper and storing values of all the paths and just checking which is giving the max value? But i think this approach is not good as it is checking all the paths and also complexity would be very high. Is there any optimal solution for that which will give correct answer in all the cases?

well @dtalamas24 posted link to topcoder where is similar problem with three paths. This can be used to solving it optimaly.

@vikasnitt. did u get any solution? If yes, then please share it.