Ex47 礼物的最大价值

题目描述

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

解题思路

这题使用动态规划，公式如下： \(f(i,\ j)\ = \ max(f(i\ -\ 1,\ j),\ f(i,\ j\ -\ 1))\ +\ grid(i,\ j)\) 另外，优化了一些内存，只保存了前一行作为。

代码

class Solution {
 public:
  int maxValue(std::vector<std::vector<int>>& grid) {
    int cols = grid[0].size();
    std::vector<int> res(cols, 0);
    for (int i = 0; i < grid.size(); ++i) {
      for (int j = 0; j < cols; ++j) {
        int left = 0, up = 0;
        if (i > 0) up = res[j];
        if (j > 0) left = res[j - 1];
        res[j] = (left > up ? left : up) + grid[i][j];
      }
    }
    return res[cols - 1];
  }
};

结果

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了86.13%的用户

内存消耗：9.4 MB, 在所有 C++ 提交中击败了48.01%的用户