[leetcode refers to offer 47. Maximum value of gift (medium)]

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 1:

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

Tips ：

0 < grid.length <= 200
0 < grid[0].length <= 200

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The problem solving process ：

Dynamic programming

class Solution {
    
    public int maxValue(int[][] grid) {
    
        int m=grid.length,n=grid[0].length;
        int dp[] = new int[n+1];
        int max = grid[0][0];
        for(int i=1;i<=m;i++){
    
            for(int j=1;j<=n;j++){
    
                dp[j] = Math.max(dp[j-1],dp[j]) + grid[i-1][j-1];
            }
        }
        return dp[n];
    }
}

Execution results ：