[剑指 Offer 47.] 礼物的最大价值
发布日期:2021-05-10 06:33:44 浏览次数:22 分类:精选文章

本文共 1339 字,大约阅读时间需要 4 分钟。

在一个 m*n 的棋盘上,每一格都有一个礼物,礼物的价值大于0。我们可以从左上角开始,每次向右或向下移动一格,直到到达右下角。目标是计算最多能拿到的礼物价值。

代码解释

class Solution {    public:        int maxValue(vector
> grid) { int row = grid.size(); int col = grid[0].size(); if (row <= 0 || col <= 0) { return 0; } // 预处理:左边累加和 for (int i = 1; i < row; ++i) { grid[i][0] += grid[i-1][0]; } // 预处理:上面累加和 for (int i = 1; i < col; ++i) { grid[0][i] += grid[0][i-1]; } // 计算路径最大值 for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { grid[i][j] += max(grid[i-1][j], grid[i][j-1]); } } return grid[row-1][col-1]; }}

代码逻辑

  • 预处理阶段

    • 先对每一行的左边元素进行累加,使得每一行第一个元素包含该行前面所有元素的和。
    • 然后对每一列的上面元素进行累加,使得每一列的第一个元素包含该列前面所有元素的和。
  • 动态规划求解

    • 从左上角开始,每个位置(i, j)的价值是其上方和左侧的最大值之和加上自身价值。
    • 通过预处理,我们可以确保每次计算到达某个位置的最大礼物价值,同时避免重复计算,提高效率。
  • 最终结果

    • 最终返回右下角位置的最大价值,即为最多能拿到的礼物价值。
  • 样例测试

    假设一个2x2的棋盘,礼物价值如下:

    1 23 4
    • 预处理阶段:
      • 第2行第1列:3 + 1 = 4
      • 第1行第2列:2 + 1 = 3
    • 动态规划求解:
      • 右下角价值:4 + max(3, 4) = 8
    • 返回结果为8。

    优化点

    • 预处理阶段:通过两个循环分别处理行和列的累加,确保每一个中间节点的计算基于正确的前置数据。
    • 动态规划阶段:通过取最大值确保路径的正确性,只走收益最大的路径。

    该算法的时间复杂度为O(n*m),适用于所有尺寸的棋盘。动态规划的方法确保了在路径依赖的问题中正确求解最大价值。

    上一篇:【春招】十大经典排序算法
    下一篇:[剑指 Offer 46.] 把数字翻译成字符串

    发表评论

    最新留言

    留言是一种美德,欢迎回访!
    [***.207.175.100]2025年04月25日 13时10分34秒