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.
