剑指 Offer 47. 礼物的最大价值

image.png
image.png

图片转自 https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vr32s/

遍历

执行用时：3 ms, 在所有 Java 提交中击败了77.52% 的用户 内存消耗：40.5 MB, 在所有 Java 提交中击败了99.04% 的用户

  1. public class Solution {
  3.     // 从地图的左上角开始往右或往下走
  4.     // 使用 grid[i][j] 记录最大值
  5.     // 当 i == 0 & j == 0 时，grid[i][j] 等于本身
  6.     // 当 i == 0 & j != 0 时，grid[i][j] 只能等于上方块加自身
  7.     // 当 i != 0 & j == 0 时，grid[i][j] 只能等于左方块加自身
  8.     // 当 i != 0 & j != 0 时，grid[i][j] 等于左方块和上方块中较大值加自身
  9.     public int maxValue(int[][] grid) {
  11.         // 从上往下
  12.         for (int i = 0; i < grid.length; i++)
  13.             // 从左往右
  14.             for (int j = 0; j < grid[0].length; j++)
  15.                 // 如果是 {0, 0}
  16.                 if (i == 0 && j == 0) continue;
  17.                 // 如果 i == 0 & j != 0 上方块加自身
  18.                 else if (i == 0) grid[i][j] += grid[i][j - 1];
  19.                 // 如果 i != 0 & j == 0 左方块加自身
  20.                 else if (j == 0) grid[i][j] += grid[i - 1][j];
  21.                 // 如果 i != 0 & j != 0 取左方块和上方块的较大值加自身
  22.                 else grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
  23.         // 返回地图的右下角
  24.         return grid[grid.length - 1][grid[0].length - 1];
  25.     }
  26. }

遍历，if 块的另外一种写法

执行用时：3 ms, 在所有 Java 提交中击败了77.52% 的用户 内存消耗：41 MB, 在所有 Java 提交中击败了68.73% 的用户

  1. class Solution {
  2.     public int maxValue(int[][] grid) {
  3.         int totalRow = grid.length;
  4.         int totalCol = grid[0].length;
  6.         for (int i = 0; i < totalRow; i++) {
  7.             for (int j = 0; j < totalCol; j++) {
  8.                 int curValue = grid[i][j];
  9.                 if (i > 0 && j > 0) {
  10.                     grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + curValue;
  11.                 } else if (i > 0) {
  12.                     grid[i][j] = curValue + grid[i - 1][j];
  13.                 } else if (j > 0) {
  14.                     grid[i][j] = curValue + grid[i][j - 1];
  15.                 }
  16.             }
  17.         }
  18.         return grid[totalRow - 1][totalCol - 1];
  19.     }
  20. }