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}
这样最终我们把空间复杂度从O(MN)降到O(1)。
联系客服