题目链接

LeetCode

题目描述

在一个 mn 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到*右下角结束。给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘

  1. 1    10   3    8
  2. 12   2    9    6
  3. 5    7    4    11
  4. 3    7    16   5

礼物的最大价值为 1+12+5+7+7+16+5=53。

解题思路

动态规划

根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。
设 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)

因此，可用动态规划解决此问题，以上公式便为转移方程。
47. 礼物的最大价值 - 图1

动态规划解析：
  • 状态定义： 设动态规划矩阵 dpdp ，dp(i,j)dp(i,j) 代表从棋盘的左上角开始，到达单元格 (i,j)(i,j) 时能拿到礼物的最大累计价值。
  • 转移方程：
  1. 当 i = 0 且 j = 0 时，为起始元素；
  2. 当 i = 0 且 j = 0 时，为矩阵第一行元素，只可从左边到达；
  3. 当 i != 0 且 j = 0 时，为矩阵第一列元素，只可从上边到达；
  4. 当 i != 0 且 j != 0 时，可从左边或上边到达；
  • 初始状态： dp[0][0] = grid[0][0] ，即到达单元格 (0,0) 时能拿到礼物的最大累计价值为 grid[0][0] ；
  • 返回值： dp[m-1][n-1]] ，m, n 分别为矩阵的行高和列宽，即返回 dp 矩阵右下角元素。

image.png

空间复杂度优化：
  • 由于 dp[i][j] 只与 dp[i-1][j] , dp[i][j-1] , grid[i][j] 有关系，因此可以将原矩阵 grid 用作 dp 矩阵，即直接在 grid 上修改即可
  • 应用此方法可省去 dp 矩阵使用的额外空间，因此空间复杂度从 O(MN) 降至 O(1) 。
  1. class Solution {
  2. public:
  3.     int maxValue(vector<vector<int>>& grid) {
  4.         int row=grid.size(),col=grid[0].size();
  5.         if(row==0||col==0)
  6.             return 0;
  7.         for(int i=0;i<row;i++)
  8.             for(int j=0;j<col;j++){
  9.                 if(i==0&&j==0)
  10.                     continue;
  11.                 else if(i==0)
  12.                     grid[i][j] = grid[i][j] + grid[i][j-1];
  13.                 else if(j==0)
  14.                     grid[i][j] = grid[i][j] + grid[i-1][j];
  15.                 else
  16.                     grid[i][j] = grid[i][j] + max(grid[i][j-1],grid[i-1][j]);
  17.             }
  18.         return grid[row-1][col-1];
  19.     }
  20. };
  • 时间复杂度 O(MN) ： M, N 分别为矩阵行高、列宽；动态规划需遍历整个 gridgrid 矩阵，使用 O(MN) 时间。
  • 空间复杂度 O(1) ： 原地修改使用常数大小的额外空间。