题目

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例

  1. 输入: 
  2. [
  3.   [1,3,1],
  4.   [1,5,1],
  5.   [4,2,1]
  6. ]
  7. 输出: 12
  8. 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

解析

动态规划
声明状态数组dp是一个 m*n 的二维数组。dp[i][j]的默认值是 0，它的含义是：在坐标点（i，j）处，能得到的最大价值礼物。所以，整个棋盘的最大价值礼物就是 dp[m-1][n-1] 的值

状态转移的过程：

  • 出发点是左上角，且只能向右/下移动，所以第一列和第一行中的 dp 值，就等于：当前礼物价值+上一个 dp 值

  • 对于一般坐标（i，j），dp[i][j] = grid[i][j] + max(dp[i - 1][j], dp[i][j - 1])

    1. var maxValue = function(grid) {
    2.   const rowNum = grid.length;
    3.   const colNum = grid[0].length;
    4.   const dp = [];
    5.   for (let i = 0; i < rowNum; ++i) {
    6.       dp[i] = [];
    7.       for (let j = 0; j < colNum; ++j) {
    8.           dp[i][j] = 0;
    9.       }
    10.   }
    12.   dp[0][0] = grid[0][0];
    13.   for (let i = 1; i < rowNum; ++i) {
    14.       dp[i][0] = grid[i][0] + dp[i - 1][0];
    15.   }
    17.   for (let j = 1; j < colNum; ++j) {
    18.       dp[0][j] = grid[0][j] + dp[0][j - 1];
    19.   }
    21.   for (let i = 1; i < rowNum; ++i) {
    22.       for (let j = 1; j < colNum; ++j) {
    23.           dp[i][j] = grid[i][j] + Math.max(dp[i - 1][j], dp[i][j - 1]);
    24.       }
    25.   }
    27.   return dp[rowNum - 1][colNum - 1];
    28. };