目录
一、题目描述
在一个 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
二、思路讲解
对于我这种算法小白来说，一步一步往下走的题一律视作动态规划。那么动态规划就需要找到递推式。
我们不难发现，右下角的最大价值其实是max{上面一格的最大值，左边一格的最大值} ，因此，我们建立数组dp，dp[i][j]表示到达(i,j)时的最大价值。
下面就是考虑边界问题，在最左边的时候，价值只跟上面一格有关；在最上面的时候，价值只跟左边一格有关；左上角的顶点最大价值就是他本身。
三、Java代码实现
class Solution {
public int maxValue(int[][] grid) {
//dp[i][j]表示到达(i,j)时的最大数
int [][]dp = new int [grid.length][grid[0].length];
dp[0][0] = grid[0][0];
for(int i=0; i<grid.length; i++) {
for(int j=0; j<grid[0].length; j++) {
if(i==0 && j!=0) { //考虑上边边界
dp[i][j] = dp[i][j-1] + grid[i][j];
} else if(i!=0 && j==0) { //考虑左边边界
dp[i][j] = dp[i-1][j] + grid[i][j];
} else if(i!=0 && j!=0) {
dp[i][j] = dp[i][j-1]>dp[i-1][j] ? dp[i][j-1] : dp[i-1][j];
dp[i][j] = dp[i][j] + grid[i][j];
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
四、时空复杂度分析
时间复杂度： 平方阶 要将二维数组遍历一遍
空间复杂度： 平方阶 使用一个二维数组
五、代码优化
1、优化空间
因为在dp数组中我们只使用每一格的上面一格和左边一格，grid数组只使用当前一格 ，所以我们可以无需申请dp数组，直接将grid数组覆盖即可
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0)
continue;
if(i == 0)
grid[i][j] += grid[i][j - 1] ;
else if(j == 0)
grid[i][j] += grid[i - 1][j];
else
grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];
}
}
空间复杂度可以降为常量阶
2、比较次数优化
由于二维数组中处于边界的格子是少数，而在我们的算法中每一个格子都要判断是否处于两条边界上，显然浪费了时间。
我们可以先把第一行和第一列初始化出来，这样就可以省去判断的时间。
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int j = 1; j < n; j++) // 初始化第一行
grid[0][j] += grid[0][j - 1];
for(int i = 1; i < m; i++) // 初始化第一列
grid[i][0] += grid[i - 1][0];
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
return grid[m - 1][n - 1];
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125072.html
