
[剑指 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),适用于所有尺寸的棋盘。动态规划的方法确保了在路径依赖的问题中正确求解最大价值。
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2025年04月25日 13时10分34秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
第一节 docker安装
2019-03-15
Linux系统时间与硬件时间及时间同步
2019-03-15
maven 必会常用命令
2019-03-15
Spring 和 DI 依赖注入
2019-03-15
Java json 数据格式封装
2019-03-15
中序线索二叉树的遍历
2019-03-15
文字策略游戏 android studio(学习intent,textview,等等)
2019-03-15
laravel server error 服务器内部错误
2019-03-15
17_注册Github账号
2019-03-15
gcc编译c文件生成可执行文件
2019-03-15
Linux驱动实现GPIO模拟I2C读写操作
2019-03-15
python爬取中庸词诗词保存mysql数据库源码
2019-03-15
java mysql大学生求职网站没有后台管理源码
2019-03-15
React超级开发指南
2019-03-15
.Net Core API的一个Json转换Help类
2019-03-15
MSSQL/SQLServer中UPDATE或INSERT依次递增做假数据的实现
2019-03-15
Jquery中的正则表达式
2019-03-15