@Mridul Thats correct. You can however optimize on space complexity. At any point of time you need only current max row and previous max row, so you can manage with only 2 rows (in fact just 1 if you optimize furthure).
On Sun, Oct 3, 2010 at 1:02 PM, Mridul Malpani <[email protected]>wrote: > @anand: the greedy appoach will not work in this test case: > {2,10,25, > 1,20,10, > 100, 5, 100} > > i think use DP. create an 'max matrix of same order. > max[i,j]= maximum( max[i-1][j] + a[i][j], max[i][j-1]+a[i][j] ); > > max[n-1][n-1] will be the answer. > > Tell me if i m wrong. > > > On Oct 2, 10:29 pm, Anand <[email protected]> wrote: > > Since in our case starting point is fixed "ie top left corner" so dynamic > > programmng will not make any difference. Dynamic programing makes > difference > > only when starting point is not fixed. Solution from Greedy and Dynamic > > programming will be same in this case. Correct me if I am wrong > > > > On Sat, Oct 2, 2010 at 8:27 AM, Mridul Malpani <[email protected] > >wrote: > > > > > @ anand: the code u have given is an greedy approach. & it will not > > > work. > > > > > On Oct 1, 12:34 am, Anand <[email protected]> wrote: > > > > Here is a code for solving the problem using DP. > > >http://codepad.org/AoPtCmwA > > > > > > On Thu, Sep 30, 2010 at 3:01 AM, Modeling Expert < > > > > > > [email protected]> wrote: > > > > > recurssion... > > > > > > > At any point X > > > > > > > val_t getMax( position X){ > > > > > > > ( ! End of Table ) > > > > > sum = GetApples[X] + MAX ( getMax(X_down) , getMax > > > > > ( X_right) ) ; > > > > > > > returnn sum ; > > > > > } > > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to [email protected]. > > > > > To unsubscribe from this group, send email to > > > > > [email protected]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[email protected]> > > > > > <algogeeks%[email protected]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[email protected]> > > > > > > > > > . > > > > > 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]<algogeeks%[email protected]> > <algogeeks%[email protected]<algogeeks%[email protected]> > > > > > . > > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
