剑指 Offer 47. 礼物的最大价值

一、题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。

你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

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

二、题目解析

为了帮助你更好的理解整个过程,我特意做了一组动画,点开可以查看

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
class Solution {
    public int maxValue(int[][] grid) {

        // row 表示有多少行
        int row = grid.length;

        // col 表示每一行有多少个元素,即 col 表示有多少列
        int col = grid[0].length;

        // dp[0][0] 表示从左上角开始,到达单元格(0 ,0)可以拿到的最大价值
        // dp[0][i] 表示从左上角开始,到达单元格(0 ,i)可以拿到的最大价值
        // dp[j][0] 表示从左上角开始,到达单元格(j ,0)可以拿到的最大价值
        // dp[i][j] 表示从左上角开始,到达单元格(i ,j)可以拿到的最大价值
        int[][] dp = new int[row][col];

        // 初始化 dp[0][0],由于只有一个元素
        // 所以 dp[0][0] 的最优解就是 grid[0][0] 这个元素
        dp[0][0] = grid[0][0];

        // i 从 1 遍历到 n - 1 
        // 获取第 0 行中第 i 列的最优解
        // 由于每次只能向下或者向右移动一步,此时只能向右移动一步
        for(int i = 1; i < col; i++){ 

            // 所以对于只有一行的情况,当前位置的最优解等于前一列的最优解加上该列的值
            dp[0][i] = dp[0][i-1] + grid[0][i];

        }

        // j 从 1 遍历到 n - 1 
        // 获取第 j 行中第 0 列的最优解
        for(int j = 1; j < row; j++){

            // 所以对于只有一列的情况,当前位置的最优解等于前一行的最优解加上该行的值
            dp[j][0] = dp[j-1][0] + grid[j][0];

        }

        // 接下来从第 1 行到第 m - 1 行
        // 从第 1 列到底 n - 1 列
        // 填充二维数组 grid 里面的值
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){

                // 由于每次只能向下或者向右移动一步
                // 位置 (i,j) 的最优解
                // 等于当前位置上方位置(i-1,j)的最优解和左侧位置(i,j-1)的最优解的较大值
                // 再加上当前位置的值
                int max = Math.max(dp[i-1][j],dp[i][j-1]);

                 // 把较大值和当前礼物相加
                dp[i][j] = max + grid[i][j];
            }
        }

        // 返回从起始位置到最后一个位置的最大礼物价值
        return dp[row - 1][col - 1]; 
    }
}