Maximum Coin Collection in a Grid

A robot is placed in the top-left corner of an R × C grid. Each cell of the grid contains a non-negative integer representing the number of coins available at that cell. The robot can only move either right or down at any step. Your task is to determine the maximum number of coins the robot can collect when it travels from the top-left corner to the bottom-right corner.

The optimal solution can be computed using dynamic programming. In particular, let \(dp(i, j)\) be the maximum coins collected to reach cell \((i, j)\). Then, the recurrence relation is given by:

[ dp(i,j) = matrix[i][j] + \max\begin{cases} dp(i-1, j) & \text{if } i > 0, \ dp(i, j-1) & \text{if } j > 0 \end{cases} ]

For the cells along the first row or first column, there is only one direction to come from. The final answer is \(dp(R-1, C-1)\), which is the value computed at the bottom-right cell.

inputFormat

The input is read from standard input (stdin) and has the following format:

R C
row1_element1 row1_element2 ... row1_elementC
row2_element1 row2_element2 ... row2_elementC
...
rowR_element1 rowR_element2 ... rowR_elementC

Here, R and C are two integers representing the number of rows and columns in the grid, respectively. Each of the next R lines contains C space-separated integers representing the coins in that row.

outputFormat

Output to standard output (stdout) a single integer representing the maximum number of coins that can be collected along a valid path from the top-left to the bottom-right corner of the grid.

3 3
1 2 3
4 5 6
7 8 9

29