His solution is based on finding the maximum value that can be reached from (0,0) to any (x,y) in the matrix. Before storing the value, check with previous max to the cell..
On Sun, Aug 21, 2011 at 4:04 PM, 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. > -- Regards, Dinoj -- 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.
