剑指 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];
}
}
