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.
