We need not necessarily pick the apple. We need to suggest a way that could have maximum apples and path need not be longest. Another person will follow our path and pick the apples.
we can start from specified (i,j) and have to reach specified (i, n) traversing either top, right, down(not left). Can greedy approach work if we take a graph and try to implement shortest path algorithm(in this case max apples) from (i, j) to (i,n)? - Azhar. On Wed, Dec 14, 2011 at 6:07 PM, Gene <gene.ress...@gmail.com> wrote: > Longest path won't work so well because it will return infinity if a > path contains a positive cycle, which doesn't apply here because once > you pick up an apple, it's gone. > > On Dec 13, 7:17 am, vikas <vikas.rastogi2...@gmail.com> wrote: > > Graph > > take up, right and bottom as nodes connected to current and do find > > max path. > > > > On Dec 13, 3:44 pm, Azhar Hussain <azhar...@gmail.com> wrote: > > > > > > > > > We have apples arranged in a mxn matrix. We start from the upper left > > > corner and have to reach bottom right corner with maximum apples. We > can > > > only move either down or right. > > > Now if we can start any where in the matrix and have to reach > anywhere on > > > the right(reach n column). We can either up, down, right(but not > left). We > > > have to collect maximum apples from a given location. > > > I am trying to solve problem. solution for the first one is given > athttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg. > > > What data structure would be suitable for the second problem and will > > > dynamic programming work. > > > > > Thanks in advance. > > > Azhar. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
