【剑指OFFER】47. 礼物的最大价值
发布日期:2021-06-29 19:46:51
浏览次数:3
分类:技术文章
本文共 691 字,大约阅读时间需要 2 分钟。
题目:在一个 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(int[][] grid) { //dp(i, j) = max{dp(i - 1, j), dp(i, j - 1)} + grid[i][j] //滚动数组 int [] dp = new int[grid[0].length + 1]; for(int i = 1; i <= grid.length; i++){ for(int j = 1; j <= grid[0].length; j++){ dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1]; } } return dp[grid[0].length]; }}
转载地址:https://darkness.blog.csdn.net/article/details/115336486 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月11日 02时50分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
The Book of QT4 翻译:1.2 布局,对象层级和内存管理
2019-04-30
麒麟信安UniKylin3.3安装配置pyqt5运行环境
2019-04-30
linux中python3 pip快速搭建pyqt5环境
2019-04-30
泛型程序设计
2019-04-30
Java集合
2019-04-30
Java List集合
2019-04-30
Java Set集合 HashSet TreeSet
2019-04-30
Java Map集合
2019-04-30
ASCII、ISO-8859-1和GB系列编码
2019-04-30
Unicode及UTF-8、UTF-16、UTF-32
2019-04-30
UCS-2、UCS-4
2019-04-30
Unicode和UCS
2019-04-30
Java如何给ServerSocket绑定指定IP地址
2019-04-30
IPv4地址的分配原理
2019-04-30
IP地址0.0.0.0表示什么
2019-04-30
ps命令和客户端显示结果详细解释
2019-04-30
进程间的通信和管道
2019-04-30
父子进程使用mmap进程间通信
2019-04-30
C++基础知识一
2019-04-30
C++基础知识二
2019-04-30