[sword finger offer] 47 Maximum value of gifts

The finger of the sword Offer 47. The greatest value of gifts

subject

  In a m*n There is a gift in every space of the chessboard , Every gift has a certain value （ Value greater than 0）. You can start from the top left corner of the chessboard to get the gifts in the grid , And move right or down one space at a time 、 Until you reach the bottom right corner of the chessboard . Given the value of a chessboard and its gifts , Please calculate the maximum value of gifts you can get ？

Ideas

• State definition ： Let's set the dynamic programming matrix dp,dp(i,j) Represents starting from the upper left corner of the chessboard , Reach cell (i,j) The maximum cumulative value of a gift when you get it .
• Transfer equation ：
  • When i = 0 And j = 0 when , Is the starting element
  • When i = 0 And j != 0 when , First row element of matrix , It can only be reached from the left
  • When i != 0 And j = 0 when , The first column of the matrix , It can only be reached from the top
  • When i != 0 And j != 0 when , It can be reached from the left or above

Code

class Solution {
    
    public int maxValue(int[][] grid) {
    
        int m = grid.length,n = grid[0].length;//  Take out the number of rows or columns of the matrix 

        for(int i = 0; i < m; i++)
        {
    
            for(int j = 0; j < n; j++)
            {
    
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] = grid[i][j] + grid[i][j - 1];//  From the left to 
                else if(j == 0) 
                {
    
                    grid[i][j] = grid[i][j] + grid[i - 1][j];
                }
                else{
    
                    grid[i][j] += Math.max(grid[i][j - 1],grid[i - 1][j]);
                }
            }
        }
        return grid[m - 1][n - 1];
    }
}