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.
