47. 礼物的最大价值

47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例：
输入:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：
0 < grid.length <= 200
0 < grid[0].length <= 200

题目分析：规划出最优路线，得到最大值；一般这种情况优先考虑使用动态规划来做，因为动态规划就是为了解决最优化问题的一种常见策略
所以结论就是：dp[rows-1][cols-1] 二维矩阵

时间复杂度:O(MN) M,N 分别为矩阵行高、列宽；动态规划需遍历整个 grid 矩阵，使用O(MN) 时间
空间复杂度:O(1) 原地修改使用常数大小的额外空间

逻辑分析.png

class Solution {

    public int maxValue(int[][] grid) {
        
        //0.初始化动态规划所需要的数据结构
        int rows = grid.length;//行
        int cols = grid[0].length;//列
        int[][] dp = new int[rows][cols];
        //00这个位置比较特殊 需要先求出来
        dp[0][0] = grid[0][0];

        //1.求出第0行 第0列的值
        for(int col = 1; col < cols;col++) {
            dp[0][col] = dp[0][col-1] + grid[0][col];
        }

        for(int row = 1;row < rows; row++) {
           dp[row][0]  = dp[row-1][0] + grid[row][0];
        }
        
        //2.求出其他行跟列的值 并把最大值存起来
        for(int row = 1;row < rows;row++) {
            for(int col = 1;col < cols;col++) {
                //从当前位置的上和左两个位置找出最大值 + 当前位置的值 就计算出当前最大价值
                dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]) + grid[row][col];
            }
        }

        //3.返回结果
        return dp[rows-1][cols-1];
        
    }
}

执行结果.png

更简洁的方式：

class Solution {

    public int maxValue(int[][] grid) {
        
        //0.初始化动态规划需要的数据结构
        int rows = grid.length;//行
        int cols = grid[0].length;//列
        int[][] dp = new int[rows+1][cols+1];

        //1.求出其他行列的值 并把最大值存起来
        for(int row = 1; row <= rows;row++){
            for(int col = 1;col <= cols;col++){
                //从当前位置的上或左两个位置找出最大值 + 当前位置的值 = 当前最大值
                dp[row][col] = Math.max(dp[row-1][col],dp[row][col-1]) + grid[row-1][col-1];
            }
        }

        //2.返回结果
        return dp[rows][cols];
        
    }
}

执行结果.png