剑指 Offer 47. 礼物的最大价值
本身的值
加上上边 / 左边 中的最大值
,然后每次遍历都可以复用上一次的值。因此我们可以得到状态转移方程:
grid
中的坐标都要减去 1,因为我们是从 1 开始的:class Solution { public int maxValue(int[][] grid) { int row = grid.length; int col = grid[0].length; // 创建dp数组,让 row 和 col 都多创建一行就可以避免判断边界值问题 int dp[][] = new int[row+1][col+1]; for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) { // 这里的 grid 中 i-1 和 j-1 是因为我们是从 1 开始的,所以要减去 1 才是原始正确的位置 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]; } } // 最后直接返回数组右下角值即可 return dp[row][col]; } }
class Solution { public int maxValue(int[][] grid) { int row = grid.length; int col = grid[0].length; // 先初始化边界 for (int i = 1; i < row; i++) { grid[i][0] += grid[i-1][0]; } for (int i = 1; i < col; i++) { grid[0][i] += grid[0][i-1]; } // 遍历 for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { // 选择左边或者上边 grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]); } } // 最后直接返回数组右下角值即可 return grid[row-1][col-1]; } }