Pengjielee's blog

题目

在一个 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

设 f(i,j) 为从棋盘左上角走至单元格 (i,j) 的礼物最大累计价值，易得到以下递推关系：f(i,j) 等于 f(i,j-1) 和 f(i-1,j) 中的较大值加上当前单元格礼物价值 grid(i,j) 。

f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)

作者：jyd 链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/solution/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

参考1：滚动数组

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxValue = function (grid) {
  const rows = grid.length,
    columns = grid[0].length;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < columns; 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[rows - 1][columns - 1];
};

参考2：滚动数组优化

var maxValue = function (grid) {
  const rows = grid.length,
    columns = grid[0].length;

  //初始化第一行
  for(let j = 1; j < columns; j++){
  	grid[0][j] += grid[0][j-1];
  }

  //初始化第一列
  for(let j = 1; j < rows; j++){
  	grid[i][0] += grid[i-1][0];
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < columns; j++) {
      grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
    }
  }
  
  return grid[rows - 1][columns - 1];
};

参考3：动态规划

var maxValue = function (grid) {
  if (grid === null || grid.length === 0 || grid[0].length === 0) {
    return 0;
  }
  const rows = grid.length,
    columns = grid[0].length;

  // 创建二维dp数组
  // dp[i][j] 从(0,0)到(i,j)时的最大价值
  const dp = Array.from({ length: rows }, (x) =>
    Array.from({ length: columns })
  );

  dp[0][0] = grid[0][0];

  // 初始化行
  for(let i = 1; i < rows; i++){
  	dp[i][0] = grid[i][0] + dp[i-1][0];
  }

  // 初始化列
  for(let j = 1; j < columns; j++){
  	dp[0][j] =  grid[0][j] + dp[0][j-1];
  }

  for (let i = 1; i < rows; i++) {
    for (let j = 1; j < columns; j++) {
      dp[i][j] = grid[i][j] +  Math.max(dp[i][j - 1], dp[i - 1][j]);
    }
  }

  return dp[rows - 1][columns - 1];
};