LeetCode C++ 剑指 Offer 47. 礼物的最大价值【Dynamic Programming】中等
发布日期:2021-07-01 02:58:44
浏览次数:2
分类:技术文章
本文共 2844 字,大约阅读时间需要 9 分钟。
在一个 m * n
的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
示例 1:
输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示:
0 < grid.length <= 200
0 < grid[0].length <= 200
解法 动态规划
class Solution { public: int maxValue(vector>& grid) { if (grid.empty()) return 0; int m = grid.size(), n = grid[0].size(); vector > dp(m, vector (n)); //dp[i][j]表示从grid[0][0]到grid[i][j]得到的最大价值 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) dp[i][j] = grid[i][j]; else if (i == 0) dp[i][j] = dp[i][j - 1] + grid[i][j]; else if (j == 0) dp[i][j] = dp[i - 1][j] + grid[i][j]; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[m - 1][n - 1]; }};
一次性通过,运行效率如下:
执行用时:16 ms, 在所有 C++ 提交中击败了85.59% 的用户内存消耗:9.6 MB, 在所有 C++ 提交中击败了28.22% 的用户
类似于01背包,空间优化如下:
class Solution { public: int maxValue(vector>& grid) { if (grid.empty()) return 0; int m = grid.size(), n = grid[0].size(); vector > dp(2, vector (n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (i == 0 && j == 0) dp[i & 1][j] = grid[i][j]; else if (i == 0) dp[i & 1][j] = dp[i & 1][j - 1] + grid[i][j]; else if (j == 0) dp[i & 1][j] = dp[!(i & 1)][j] + grid[i][j]; else dp[i & 1][j] = max(dp[!(i & 1)][j], dp[i & 1][j - 1]) + grid[i][j]; } } return max(dp[0][n - 1], dp[1][n - 1]); }};
更简洁的写法如下:
class Solution { public: int maxValue(vector>& grid) { if (grid.empty()) return 0; int m = grid.size(), n = grid[0].size(); vector > dp(2, vector (n + 1)); //空间+1 for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) dp[i & 1][j + 1] = max(dp[!(i & 1)][j + 1], dp[i & 1][j]) + grid[i][j]; return max(dp[0][n], dp[1][n]); }};
运行效率如下:
执行用时:12 ms, 在所有 C++ 提交中击败了98.51% 的用户内存消耗:9.2 MB, 在所有 C++ 提交中击败了77.27% 的用户
继续优化空间:
class Solution { public: int maxValue(vector>& grid) { if (grid.empty()) return 0; int m = grid.size(), n = grid[0].size(); vector dp(n + 1); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) dp[j + 1] = max(dp[j], dp[j + 1]) + grid[i][j]; return dp[n]; }};
运行效率如下:
执行用时:12 ms, 在所有 C++ 提交中击败了98.51% 的用户内存消耗:9.2 MB, 在所有 C++ 提交中击败了77.27% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/111714419 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月13日 05时20分45秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Go语言并发组件
2019-05-01
简析STUN协议
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01
Debug 和 Release 编译方式的本质区别
2019-05-01
struts返回xml数据例子
2019-05-01
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
LINUX CP命令详解
2019-05-01
source insight快捷键及使用技巧
2019-05-01
映 射 ALT 键
2019-05-01
vim使用快捷键F4生成文件头注释、F5生成main函数模板、F6生成.h文件框架模板
2019-05-01
用python解析html
2019-05-01
OV5620的视频驱动
2019-05-01
C++中两个类交叉定义或递归定义的解决办法
2019-05-01
ECharts is not Loaded解决方案
2019-05-01
echarts切换tab时,第一个图表显示,第二个图表不显示的解决办法
2019-05-01
记一次Hive 行转列 引起的GC overhead limit exceeded
2019-05-01