it can also be done if we calculate values diagonal wise in the matrix. At each step choose maximum value , at last we'll get maximum value.
Sanju :) On Sun, Aug 21, 2011 at 6:59 PM, sarvesh saran <[email protected]>wrote: > Hi Nagaraj, > > Should it not be: > > (a[i+1][j],a[i][j+1])+a[i][j] ? That is given (i,j) find max of next 2 > possible cells? > > Why are we subtracting instead of adding? > > > thanks, > Sarvesh > > > On Mon, Aug 22, 2011 at 7:11 AM, nagarajan <[email protected]> wrote: > >> Just its a matrix manipulation .. similar to knap sack problem... >> >> >> i am filling each value of matrix by finding the max >> (a[i-1][j],a[i][j-1])+a[i][j] .. >> >> >> so that the max value will be stored in the each index positions and so >> in the a[M][N].. >> >> >> On Mon, Aug 22, 2011 at 1:34 AM, sarvesh saran < >> [email protected]> wrote: >> >>> Hi Nagaraj, >>> >>> Can you explain the logic behind your code? it will be a great help! >>> >>> thanks, >>> Sarvesh >>> >>> >>> >>> >>> On Mon, Aug 22, 2011 at 1:21 AM, nagarajan <[email protected]> wrote: >>> >>>> it can be done in the following way, >>>> >>>> >>>> let the input is in the array a[N+1][M+1] >>>> >>>> we process the input as >>>> >>>> 0 0 0 0 0 >>>> 0 2 2 3 0 >>>> 0 0 3 1 1 >>>> 0 1 2 2 1 >>>> 0 4 1 2 2 >>>> >>>> compute the matrix as >>>> >>>> a[i][j] = max(a[i-1][j], a[i][j-1])+a[i][j]; for i=1 to N and j=1 to M >>>> >>>> you will get the required result in a[N][M] >>>> >>>> the answer looks as >>>> >>>> 0 0 0 0 0 >>>> 0 2 4 7 7 >>>> 0 2 7 8 9 >>>> 0 3 9 11 12 >>>> 0 7 10 13 15 >>>> >>>> i think this is right... any mistakes in this , you are welcome.. >>>> >>>> On Mon, Aug 22, 2011 at 1:00 AM, sarvesh saran < >>>> [email protected]> wrote: >>>> >>>>> HI, >>>>> >>>>> I have a classic chessboard and rice problem. the detailed statement is >>>>> in the link:http://pastebin.com/nykkFP84 >>>>> >>>>> my solution is : >>>>> >>>>> 1. int max_rice(std::vector<std::vector<int>> const& board, >>>>> unsigned x, unsigned y) >>>>> 2. { >>>>> 3. if (y == board.size() || x == board[0].size()) return 0; >>>>> 4. >>>>> 5. return std::max(max_rice(board, x + 1, y), max_rice(board, x, y >>>>> + 1)) + board[y][x]; >>>>> 6. } >>>>> >>>>> I would like to find a dynamic programming solution to this problem. >>>>> Any ideas? >>>>> >>>>> thanks, >>>>> Sarvesh >>>>> >>>>> -- >>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> >>>> >>>> Nagarajan S >>>> >>>> -- >>>> 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. >>>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> >> >> Nagarajan S >> >> -- >> 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. >> > > -- > 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. > -- 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.
