当前位置: 首页 > news >正文

【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)

目录 题目&#xff1a;剑指 Offer 47. 礼物的最大价值 - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a; 题目&#xff1a;剑指 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官方举办的新星计划,这个可以让我们更快的成长,十分有价值.接下来让我们一起开始吧!如果对您有帮助的话希望能够得到您的支持和帮助,我会持续更新的!&#x1f6a9;part1:自我介绍我是一名来自…...

嵌入式学习笔记——STM32的USART收发字符串及串口中断

USART收发字符串及串口中断前言字符串的收发发送一个字符串接收字符串需求利用串口实现printf中断中断是什么前言 上一篇中&#xff0c;介绍了串口收发相关的寄存器&#xff0c;通过代码实现了一个字节的收发&#xff0c;本文接着上面的内容&#xff0c;通过功能函数实现字符串…...

数据分析之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工作 &#xff08;1&#xff09;写操作 &#xff08;2&#xff09;读操作 &#xff08;3&#xff09;帧头和帧尾的添加和除由电路自动执行 &#xff08;4&#xff09;硬件数据控制…...

leetcode:有效地括号

给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’&#xff0c;‘}’&#xff0c;‘[’&#xff0c;‘]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都…...

四等分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 翻译&#xff1a; 哈尔滨&#xff0c;这个名字最初是一个满语单词&#xff0c;意思是“晒渔网的地方”&#xff0c;从松花江边的一个小农村居民点发展成为中国东北最大的城市之一。1898年&#xff0c;随着中国东部铁路的到来&#xff0c;这座城市首先…...

Maven的下载和配置

一、前言 一般按要求下载jar ,但是jar 包版本不好控制。有时候就会jar版本不同导致项目运行的结果也有差异&#xff0c;这样在团队开发中&#xff0c;在多个项目开发的是&#xff0c;jar包还要进行拷贝&#xff0c;可能也会出现版本还jar损坏的情况&#xff0c;所以一个能统一…...

服务高并发、高性能、高可用实现方案

服务高并发、高性能、高可用实现方案 软件开发的三高指标&#xff1a;高并发、高性能、高可用。 高并发方面要求QPS 大于 10万&#xff1b;高性能方面要求请求延迟小于 100 ms&#xff1b;高可用方面要高于 99.99%(4个9) 一、高并发&#xff1a; 高并发是现在互联网分布式框架设…...

uniCloud在线升级APP配置教程

app在线升级背景实现思路流程流程背景 因用户需要添加手机h5页面来进数据操作实现思路流程 实现流程图流程 相关文档&#xff1a;帮助文档 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开发板制作的一款类似眼镜外挂的小产品&#xff0c;可以对场景进行辅助识别&#xff0c;并通过云端交互实现物联网控制&#xff0c;进一步实现物联网与人机交互的融合。 开发板配置了摄像头和小屏幕接口&#xff0c;并外…...

博客系统(界面设计)

✏️作者&#xff1a;银河罐头 &#x1f4cb;系列专栏&#xff1a;JavaEE &#x1f332;“种一棵树最好的时间是十年前&#xff0c;其次是现在” 目录实现博客列表页预期效果导航栏页面主体左右布局左侧区域右侧区域完整代码实现博客详情页预期效果导航栏 左侧右侧完整代码实现…...

素材要VIP咋整?看python大展神通

前言 嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! 再我们缺少素材的时候&#xff0c;我们第一反应 我们肯定会去网上寻找&#xff0c;但是&#xff01;&#xff01; 有的素材需要VIP&#xff01;这可咋整呢&#xff1f; 看我利用python大展神通&#xff0c;采集某图网图片…...

[ vulnhub靶机通关篇 ] 渗透测试综合靶场 DC-1 通关详解 (附靶机搭建教程)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…...

软件测试文档编写步骤

编写软件测试文档是软件测试中非常重要的一部分。以下是编写软件测试文档的一些常见步骤&#xff1a; 1.明确软件测试的目标和目的&#xff1a;在开始编写软件测试文档之前&#xff0c;需要明确测试的目标和目的。这包括定义测试的范围&#xff0c;测试的目标和测试的优先级。 …...

重新认识下网页水印

使用背景图图片 单独使用 css 实现&#xff0c;使用 backgroundImage&#xff0c;backgroundRepeat 将背景图片平铺到需要加水印的容器中即可。 如果希望实现旋转效果&#xff0c;可以借助伪元素&#xff0c;将背景样式放到伪元素中&#xff0c;旋转伪元素实现&#xff1a; &l…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...