DP problem help

What can be the optimized algorithm to solve this problem ?

Given a matrix with M rows and N columns (M x N). In each cell there’s a number of apples.
You start from the upper-left corner of the matrix. You can go down or right one cell. You need to arrive to the bottom-right corner. Then you need to go back to the upper-left cell by going each step one cell left or up. Find the maximum number of apples you can collect.When you pass through a cell - you collect all the apples left there.

Restrictions: 1 < N, M <= 50 ; each cell contains between 0 and 1000 apples inclusive

6 Likes

@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: http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static

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:

http://discuss.codechef.com/questions/19343/dp-problem-help/19374 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.