# 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…

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.

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…