i thnk it can be done using dynamic programming.. let the array b 2 5 3 2 5 1 10 2 5
now at at every point in the matrix..there can be two ways..to reach that point..either from left..or from right.. for example to reach at the center of the above matrix..we can come from 2->5->5 or 2->2->5..and can select the path that give max apples..similarly..we can calculate this..for every point in the 2D array the above matrix can be transformed into maximum apples at every point 2 7 10 4 12 13 14 16 21 for top most row and left most column..we only add..the previous value..(because we dont have second direction) for arr(1,1) we calculate the max..that is from 7 and 4..and add it to the center value..to get 12 for arr(1,2) we calculate the max ..that if rom 12 and 10 and add it to arr(1,2) to get ..13.. this is how..we can do for..arr(2,1) and arr(2,2)... this is what we can do.. correct me if am wrong..i am naive solution provider On Tue, Dec 13, 2011 at 4:14 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 at > http://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. > -- *Dheeraj Sharma* -- 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.
