一、题目描述
在一个 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]; } }
