Unable to figure out why a DP approach won't work

algorithm, dynamic-programming

Solution

Your algorithm might take bad decisions by not taking into account from start that you will have other opportunities to pick up big rewards, thus lowering your total.

Example:

S 0 0 50 1
1 1 1 0 1
1 1 1 0 1
1 1 1 50 1
1 1 1 50 E

Your algo would go S-0-0-50-0-0-50-50-E, then E-50(0)-1-1-1-1-1-1-S, then S-0-1-1-1-1-50(0)-1-E. In total you get 0 apples 7 times (total reward 3*50+7*0+11*1=161).

You can do better like that: S-0-0-50-1-1-1-1-E, then E-50-1-1-1-1-1-1-S, then S-0-1-1-1-1-50-1(0)-E, which gives you 3*150+4*0+14*1=164 apples in total.

So you can use DP, but not like that just once from S to E, then once E-S and then S-E again. You have to think the complete path at once.

Problem

I am trying to learn Dynamic Programming techniques. I am looking at this tutorial - https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/. Please read the problem statement of problem `StarAdventure` in `Advanced` section. I didn't understand why can't we just use the classic DP approach of finding best path from upper-left to bottom-right thrice removing apples found in best path each time. Can someone explain using a sample case why won't that approach work. Problem description: Given a matrix with M rows and N columns (N x M). 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. Having arrived at this upper-left cell, you need to go again back to the bottom-right cell. 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.

Original source