CODEWITHSUNDEEP
algorithmdynamic-programming
Bytemare
Bytemare

Reputation: 107

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

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.

Upvotes: 4

Views: 206

Answers (1)

gdelab
gdelab

Reputation: 6220

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.

Upvotes: 5

Related Questions