543，剑指 Offer-动态规划解礼物的最大价值

Original 博哥数据结构和算法 2022-05-01

收录于合集 #剑指offer 34个

A person who won't read has no advantage over one who can't read.

识字却不愿阅读的人，比文盲也好不到哪去。

问题描述

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

示例 1:

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

提示：

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

动态规划解决

这题可以参照409，动态规划求不同路径，第409题让求的是有多少种路径，而这题让求的是所有路径中数字和最大的值。这题很容易想到的解决方式就是动态规划。

根据题意要求我们定义dp[i][j]表示从矩阵的左上角走到坐标（i，j）所能拿到的最大礼物。

如果要走到坐标（i，j），我们可以从坐标（i-1，j）往下走一步，或者从坐标（i，j-1）往右走一步，到底应该从哪里，我们应该取这两个方向的最大值，所以

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];

那么边界条件是什么呢

如果在左上角，dp[0][0]=grid[0][0]，
如果在最上边一行，因为不能从上面走过来，只能从左边走过来，所以当前值是他左边元素的累加。
如果在最左边一列，因为不能从左边走过来，只能从上边走过来，所以当前值是他上边元素的累加。

来看下代码

 1public int maxValue(int[][] grid) {
 2    //边界条件判断
 3    if (grid == null || grid.length == 0)
 4        return 0;
 5    int m = grid.length;
 6    int n = grid[0].length;
 7    int[][] dp = new int[m][n];
 8    dp[0][0] = grid[0][0];
 9    //初始化dp的最上面一行，从左到右累加
10    for (int i = 1; i < n; i++) {
11        dp[0][i] = dp[0][i - 1] + grid[0][i];
12    }
13    //初始化dp的最左边一列，从上到下累加
14    for (int i = 1; i < m; i++) {
15        dp[i][0] = dp[i - 1][0] + grid[i][0];
16    }
17
18    //下面是递推公式的计算
19    for (int i = 1; i < m; i++) {
20        for (int j = 1; j < n; j++) {
21            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
22        }
23    }
24    return dp[m - 1][n - 1];
25}

为了方便计算我们还可以把dp的宽和高增加1，也就是dp的最上面一行和最左边一列不存储任何数值，他们都是0，这样是为了减少一些判断

 1public int maxValue(int[][] grid) {
 2    if (grid == null || grid.length == 0)
 3        return 0;
 4    int m = grid.length;
 5    int n = grid[0].length;
 6    //为了方便计算，dp的宽和高都增加了1
 7    int[][] dp = new int[m + 1][n+1];
 8    //下面是递推公式的计算
 9    for (int i = 0; i < m; i++) {
10        for (int j = 0; j < n; j++) {
11            dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
12        }
13    }
14    return dp[m][n];
15}

动态规划代码优化

我们来看一下这个公式

dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];

我们发现当前值只和左边和上边的值有关，和其他的无关，比如我们在计算第5行的时候，那么很明显第1，2，3行的对我们来说都是无用的，所以我们这里可以把二维dp改成一维的，其中dp[i][j-1]可以用dp[j-1]来表示，就是当前元素前面的，dp[i-1][j]可以用dp[j]来表示，就是上边的元素。

来看下代码

 1public int maxValue(int[][] grid) {
 2    if (grid == null || grid.length == 0)
 3        return 0;
 4    int m = grid.length;
 5    int n = grid[0].length;
 6    //数组改成一维的
 7    int[] dp = new int[n + 1];
 8    for (int i = 0; i < m; i++) {
 9        for (int j = 0; j < n; j++) {
10            dp[j + 1] = Math.max(dp[j], dp[j + 1]) + grid[i][j];
11        }
12    }
13    return dp[n];
14}

我们再来仔细看这道题，题中没说不可以修改原来数组的值，所以我还可以使用题中的二维数组来代替二维dp数组

 1public int maxValue(int[][] grid) {
 2    //边界条件判断
 3    if (grid == null || grid.length == 0)
 4        return 0;
 5    int m = grid.length;
 6    int n = grid[0].length;
 7    //初始化dp的最上面一行，从左到右累加
 8    for (int i = 1; i < n; i++) {
 9        grid[0][i] += grid[0][i - 1];
10    }
11    //初始化dp的最左边一列，从上到下累加
12    for (int i = 1; i < m; i++) {
13        grid[i][0] += grid[i - 1][0];
14    }
15
16    //下面是递推公式的计算
17    for (int i = 1; i < m; i++) {
18        for (int j = 1; j < n; j++) {
19            grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
20        }
21    }
22    return grid[m - 1][n - 1];
23}