A gift is placed on each square of an M * N board, and each gift has a value (value greater than 0). You can start at the top left of the board and move one space to the right or down until you reach the bottom right of the board. Given the value of a chess board and the gifts on it, calculate the maximum value of gifts you can get.
Example 1:
,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 12: path 1-3-5-2-1, you can get the most value of the gift
Tip:
0 < grid.length <= 200
0 < grid[0].length <= 200
Start with 0,0, and add the preceding number to each number in the first row and column. Then iterate over the other positions, adding the maximum value above and to the left of each position. Finally return to the lower right corner.
class Solution {
public int maxValue(int[][] grid) {
int low = grid.length;
int right = grid[0].length;
for (int i = 1; i < low; i++) grid[i][0] = grid[i][0] + grid[i - 1] [0];
for (int i = 1; i < right; i++) grid[0][i] = grid[0][i] + grid[0][i - 1];
for (int i = 1; i < low; i++) {
for (int j = 1; j < right; j++) {
grid[i][j] = grid[i][j] + Math.max(grid[i - 1][j], grid[i][j - 1]); }}return grid[low - 1][right - 1]; }}Copy the code