剑指 Offer 47. 礼物的最大价值（动态规划）
创始人
2025-05-30 17:27:02

题目：

链接：剑指 Offer 47. 礼物的最大价值
难度：中等
相关博文：LeetCode 64. 最小路径和（动态规划）

在一个 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

动态规划：

dp[ i ][ j ] 状态定义：从左上角位置(0, 0)走到位置(i, j)的最大价值和。

状态转移方程：dp[ i ][ j ] = max(dp[ i - 1 ][ j ] + grid[ i ][ j ], dp[ i ][ j - 1] + grid[ i ][ j ])
在遍历过程中 dp[ i ][ j ] 有两种选择：要么从左边一格[ i ][ j - 1 ]移动过来，要么从上面一格[ i - 1 ][ j ]移动过来，选择两条路中礼物价值和较大的那一条。

base case：dp[0][0] = grid[0][0]
左上角第一格是起始点，必选。

代码：

class Solution {
public:int maxValue(vector>& grid) {int m = grid.size(), n = grid[0].size();vector> dp(m, vector(n));// base casedp[0][0] = grid[0][0];for(int i = 1; i < m; ++i) dp[i][0] = dp[i - 1][0] + grid[i][0]; // 第一列特殊处理for(int j = 1; j < n; ++j) dp[0][j] = dp[0][j - 1] + grid[0][j]; // 第一行特殊处理for(int i = 1; i < m; ++i){for(int j = 1; j < n; ++j){dp[i][j] = max(dp[i-1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]); // 状态转移方程}}return dp[m - 1][n - 1];}
};

时间复杂度O(m * n），空间复杂度O(m * n)。

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：【Linux】进程的基础概念 进程的相关操作 进程的状态

下一篇：什么是算法算法的特性有哪些（什么是算法算法的特性有哪些呢） 什么叫算法算法的特征有哪些 简述算法和算法特性

相关内容

热门资讯

一尺等于多少厘米（一尺等于多少... 本篇文章极速百科给大家谈谈一尺等于多少厘米，以及一尺等于多少厘米长度对应的知识点，希望对各位有所帮助...
mg是什么意思单位（mg是什么... 今天给各位分享mg是什么意思单位的知识，其中也会对mg是什么单位g又是什么单位进行解释，如果能碰巧解...
瑞纳1.4手动真实油耗-百度有... 本篇文章极速百科给大家谈谈瑞纳1.4手动真实油耗-百度有驾，以及瑞纳14l油耗多少真实油耗对应的知识...
2012款福克斯按键介绍（20... 今天给各位分享2012款福克斯按键介绍的知识，其中也会对2012款福克斯按键功能介绍进行解释，如果能...
轻松缓存 Android + ... 轻松缓存 Android + Kotlin + Flow 技术背景 在某些情况下&...
搜索系统（二） term weight 如何衡量一个词在一篇文档中的重要性 词频率（tf）...
基于“遥感+”融合技术在碳储量... 以全球变暖为主要特征的气候变化已成为全球性环境问题，对全球可持续发展带来严峻挑战。20...
描写人物表情神态的四字词语（描... 本篇文章极速百科给大家谈谈描写人物表情神态的四字词语，以及描写人物表情神态的四字词语对应的知识点，希...
黑天鹅寓意着什么意思（黑天鹅寓... 本篇文章极速百科给大家谈谈黑天鹅寓意着什么意思，以及黑天鹅寓意着什么意思啊对应的知识点，希望对各位有...
15磅等于多少公斤,15榜是多... 15磅等于多少公斤目录15磅等于多少公斤15榜是多少kg磅和公斤是怎么换算的?15lb是多少公斤15...
Linux基本入门笔记 环境搭建 虚拟机软件：Vmware 15 pro linux版本：cen...
蔡少芬邱淑贞怎么分清（蔡少芬 ... 今天给各位分享蔡少芬邱淑贞怎么分清的知识，其中也会对蔡少芬 邱淑贞 像进行解释，如果能碰巧解决你现在...
报名CSGO/steam游戏搬... 报名CSGO/steam游戏搬砖项目前，这些内幕一定要了解 我相信大多数人都经常困惑...
二叉树的最小深度——递归法、迭... 1题目给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节...
基于java下的Springb... 基于java下的Springboot框架的=学生毕业离校系统 开发语言：Ja...
年收入四万算贫困吗 极速百科网... 年收入四万算贫困吗目录年收入四万算贫困吗年收入四万算贫困吗贫困户家庭年收入的标准是多少年收入四万算贫...
麒麟655与骁龙820谁好,骁... 麒麟655与骁龙820谁好目录麒麟655与骁龙820谁好骁龙和麒麟哪个好？820处理器与625处理器...
怎样找圆心,给你一个圆，你能至... 怎样找圆心目录怎样找圆心给你一个圆，你能至少用几种方法找到圆心如何确定圆心位置?怎样找圆心 1...
世界上著名的科学家有哪些,科学... 世界上著名的科学家有哪些目录世界上著名的科学家有哪些科学家有哪些人？6个世界上著名的科学家的名字例举...
lgsvl 现状 lgsvl自从2023年1月停服务以来，几乎就没有lgsvl最新的消息了，...
如何用深度强化学习做单元测试代... 设计一个用强化学习来生成单元测试代码的系统需要考虑以下几个方面： Agent...
STM32的推挽输出和开漏输出 文章目录 前言一、推挽输出二、开漏输出三、区别和适应场景总结 前言 本篇文章将带大家了解STM...
表示天气很冷的朋友圈说说,天气... 表示天气很冷的朋友圈说说目录表示天气很冷的朋友圈说说天气变冷的说说发朋友圈天冷了高情商朋友圈句子有哪...
太阳的结构层次由核心依次是什么... 太阳的结构层次由核心依次是什么目录太阳的结构层次由核心依次是什么太阳从内到外依次可以分成哪几个层次由...
公务员报名时照片如何处理,20... 公务员报名时照片如何处理目录公务员报名时照片如何处理2021国家公务员考试报名“照片处理工具”如何使...
iqos对人体的危害有哪些,I... iqos对人体的危害有哪些目录iqos对人体的危害有哪些I qos 电子烟的危害有没有人用过iqos...
【SQL开发实战技巧】系列（二... 系列文章目录 【SQL开发实战技巧】系列（一）:关于SQL不得不说的那些...
【面试题】有哪些良好的veri... 1.使用有意义的命名 命名应该清晰、简洁、易于理解和维护，避免使用缩写或不规范的命名方...
用友NC5X数据抽取 功能通过工具，对NC帐套中的特定公司和特定模块及年度进行抽取，形成独立的...
密度泛函理论-从波函数到电荷密... 1 在许多物理学和工程领域中，取得科学和技术进步关键在于能够从原子或者分子尺寸...