【LeetCode】剑指 Offer(24)
目录
题目:剑指 Offer 47. 礼物的最大价值 - 力扣(Leetcode)
题目的接口:
解题思路:
代码:
过啦!!!
写在最后:
题目:剑指 Offer 47. 礼物的最大价值 - 力扣(Leetcode)

题目的接口:
class Solution {
public:int maxValue(vector<vector<int>>& grid) {}
};
解题思路:
这是一道动态规划的题目,
具体思路如下:
我们将这个问题分解成一个个小问题:
看一下这个例子:

如果第一行的2是终点,那么他的最大路径是dp[0][0] + dp[0][1];
如果第二行的1是终点,那么他的最大路径是dp[1][0] + dp[0][0];
然后,
我们将这两个位置的数值,改成dp[0][0] + dp[0][1]、dp[1][0] + dp[0][0],
如下图:

那么以此类推:
如果dp[0][2]是终点,dp[0][2]就等于 dp[0][1] + dp[0][2];
如果dp[2][0]是终点,dp[2][0]就等于 dp[1][0] + dp[2][0];
如果dp[1][1]是终点,dp[1][1]就等于 max(dp[0][1], dp[1][0]) + dp[1][1]。

按照这个规律走,最后,右下角的那个就是最大路径的值。
这就是将一个大的问题,拆解成一个个小问题解决。
代码:
class Solution {
public:int maxValue(vector<vector<int>>& grid) {//这是棋盘的行和列int row = grid.size();int col = grid[0].size();//这是棋盘第一行每一格的路径的最大值计算for(int i = 1; i < col; i++){grid[0][i] = grid[0][i - 1] + grid[0][i];}//这是棋盘第一列每一格的路径的最大值计算for(int i = 1; i < row; i++){grid[i][0] = grid[i - 1][0] + grid[i][0];}//这是棋盘剩余位置的每一格作为终点的路径最大值计算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]) + grid[i][j];}}//最后返回右下角的路径最大值return grid[row - 1][col - 1];}
};
过啦!!!

写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
【LeetCode】剑指 Offer(24)
目录 题目:剑指 Offer 47. 礼物的最大价值 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 题目:剑指 Offer 47. 礼物的…...
javaEE 初阶 — CSS 元素的显示模式与盒模型
文章目录1. 元素的显示模式1.1 块级元素1.2 行内元素1.3 行内元素和块级元素的区别1.4 改变显示模式2. 盒模型2.1 边框2.1.1 边框的粗细2.1.2 边框的颜色2.1.3 边框的风格2.2 内边距2.3 外边距2.3.1 margin 的特殊情况1. 元素的显示模式 1.1 块级元素 常见的元素: h1 - h6 、…...
新星计划-我为什么要写博客?写博客的意义是什么
CSDN的各位友友们你们好,今天千泽要和大家交流一下写博客的意义,并且鼓励大家参加CSDN官方举办的新星计划,这个可以让我们更快的成长,十分有价值.接下来让我们一起开始吧!如果对您有帮助的话希望能够得到您的支持和帮助,我会持续更新的!🚩part1:自我介绍我是一名来自…...
嵌入式学习笔记——STM32的USART收发字符串及串口中断
USART收发字符串及串口中断前言字符串的收发发送一个字符串接收字符串需求利用串口实现printf中断中断是什么前言 上一篇中,介绍了串口收发相关的寄存器,通过代码实现了一个字节的收发,本文接着上面的内容,通过功能函数实现字符串…...
数据分析之Pandas(1)
3.Pandas 文章目录3.Pandas3.1 Pandas基本介绍3.1.1 Pandas的基本数据结构3.1.1.1 Pandas库的Series类型3.1.1.2 Pandas库的DataFrame类型DataFrame初始化DataFrame查看数据3.1.2 Pandas读取数据及数据操作行操作添加一行删除一行列操作增加一列删除一列通过标签选择数据条件选…...
17、江科大stm32视频学习笔记——USART串口协议和USART串口外设
目录 1、通信接口 2、 硬件电路 3、电平标准 4、串口参数及时序 5、USART简介 6、USART工作 (1)写操作 (2)读操作 (3)帧头和帧尾的添加和除由电路自动执行 (4)硬件数据控制…...
leetcode:有效地括号
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都…...
四等分list
Testpublic void s (){ int targ 4; List mList new ArrayList(); List<List> mEndList new ArrayList<>(); for (int i 0; i <34; i) { mList.add(“item” i); } // System.out.println(mList.toString()); if (mList.size() % targ ! 0) { for (int j …...
php连接sqlserver数据库
docker 安装sqlserver数据库sudo docker pull mcr.microsoft.com/mssql/server:2017-latestsudo docker run -e "ACCEPT_EULAY" -e "MSSQL_SA_PASSWORD<YourStrongPassw0rd>" -p 1433:1433 --name sqlserver --hostname sqlserver -d mcr.microsoft.…...
The 2019 China Collegiate Programming Contest Harbin Site F. Fixing Banners
Problem - F - Codeforces 翻译: 哈尔滨,这个名字最初是一个满语单词,意思是“晒渔网的地方”,从松花江边的一个小农村居民点发展成为中国东北最大的城市之一。1898年,随着中国东部铁路的到来,这座城市首先…...
Maven的下载和配置
一、前言 一般按要求下载jar ,但是jar 包版本不好控制。有时候就会jar版本不同导致项目运行的结果也有差异,这样在团队开发中,在多个项目开发的是,jar包还要进行拷贝,可能也会出现版本还jar损坏的情况,所以一个能统一…...
服务高并发、高性能、高可用实现方案
服务高并发、高性能、高可用实现方案 软件开发的三高指标:高并发、高性能、高可用。 高并发方面要求QPS 大于 10万;高性能方面要求请求延迟小于 100 ms;高可用方面要高于 99.99%(4个9) 一、高并发: 高并发是现在互联网分布式框架设…...
uniCloud在线升级APP配置教程
app在线升级背景实现思路流程流程背景 因用户需要添加手机h5页面来进数据操作实现思路流程 实现流程图流程 相关文档:帮助文档 https://uniapp.dcloud.net.cn/uniCloud/cf-functions.html 注册服务空间 https://unicloud.dcloud.net.cn/pages/login/login uni升级…...
idea常用的快捷键
idea常用的快捷键Alt回车 导入包,自动修正CtrlN 查找类CtrlShiftN 查找文件CtrlAltL 格式化代码CtrlAltO 优化导入的类和包AltInsert 生成代码(如get,set方法,构造函数等)CtrlE或者AltShiftC 最近更改的代码CtrlR 替换文本CtrlF 查找文本CtrlShiftSpace 自动补全代码Ctrl空格 代…...
全志V85x硬件设计大赛作品精选第一期,快来Pick你心目中的最佳方案
1、V853-智能交互摄像头开发板 该参赛作品基于全志V853开发板制作的一款类似眼镜外挂的小产品,可以对场景进行辅助识别,并通过云端交互实现物联网控制,进一步实现物联网与人机交互的融合。 开发板配置了摄像头和小屏幕接口,并外…...
博客系统(界面设计)
✏️作者:银河罐头 📋系列专栏:JavaEE 🌲“种一棵树最好的时间是十年前,其次是现在” 目录实现博客列表页预期效果导航栏页面主体左右布局左侧区域右侧区域完整代码实现博客详情页预期效果导航栏 左侧右侧完整代码实现…...
素材要VIP咋整?看python大展神通
前言 嗨喽~大家好呀,这里是魔王呐 ❤ ~! 再我们缺少素材的时候,我们第一反应 我们肯定会去网上寻找,但是!! 有的素材需要VIP!这可咋整呢? 看我利用python大展神通,采集某图网图片…...
[ vulnhub靶机通关篇 ] 渗透测试综合靶场 DC-1 通关详解 (附靶机搭建教程)
🍬 博主介绍 👨🎓 博主介绍:大家好,我是 _PowerShell ,很高兴认识大家~ ✨主攻领域:【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 🎉点赞➕评论➕收藏 养成习…...
软件测试文档编写步骤
编写软件测试文档是软件测试中非常重要的一部分。以下是编写软件测试文档的一些常见步骤: 1.明确软件测试的目标和目的:在开始编写软件测试文档之前,需要明确测试的目标和目的。这包括定义测试的范围,测试的目标和测试的优先级。 …...
重新认识下网页水印
使用背景图图片 单独使用 css 实现,使用 backgroundImage,backgroundRepeat 将背景图片平铺到需要加水印的容器中即可。 如果希望实现旋转效果,可以借助伪元素,将背景样式放到伪元素中,旋转伪元素实现: &l…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
