Sword finger offer series - 47 Maximum 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 ？

Example

 Input : 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
 Output : 12
 explain :  route  1→3→5→2→1  Can get the most value gifts 

Ideas

We can only go right or down one grid at a time , So the first line 、 There is only one way to go in the first column , You can open a two-dimensional array and record the first line first 、 The first column is the gift value that each grid can get , Then calculate the of the remaining lattice . Each grid should be equal to the grid above it and the grid on the left. Take a maximum value plus the value on the grid of the original array . Finally, the newly calculated value in the lower right corner is the result we want

Code

class Solution {
    
public:
    int maxValue(vector<vector<int>>& grid) {
    
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid[0].size(); i ++ ){
    
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < grid.size(); i ++ ){
    
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i ++ ) {
    
            for (int j = 1; j < n; j ++ ) {
    
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};