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

DP学习第五篇之礼物的最大价值

DP学习第五篇之礼物的最大价值

剑指 Offer 47. 礼物的最大价值 - 力扣(LeetCode)

在这里插入图片描述

一.题目解析

在这里插入图片描述

二. 算法原理

  1. 状态表示

    tips: 经验+题目要求。以[i,j]位置为结尾,。。。

dp[i][j]: 到达[i, j]位置时,此时的最大礼物价值

  1. 状态转移方程

    tips: 用之前或之后的状态,推导出dp[i]的值。根据最近的一步,来划分问题

到达[i, j]位置之前:

  • 从[i - 1, j]位置向下走一步,到[i, j]

  • 从[i, j - 1]位置向右走一步,到[i, j]

    即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + g[i][j]

  1. 初始化

    tips: 保证填表的时候不越界。增加虚拟节点
在这里插入图片描述

  • 虚拟节点里面的值,要保证后面填表是正确的

以起始位置为结尾,则要保证:第一个位置dp[1][1] = g[1][1]。此时初始化时可以选择将虚拟节点的值都设置为0,保证后续填表的正确性

  • 下标的映射关系

dp表映射到原矩阵:横纵坐标-1

  1. 填表顺序

从上往下填写每一行,每一行从左往右

  1. 返回值

题目要求:到达右下角的礼物价值

即:return dp[m][n]

三. 编写代码

class Solution {
public:int maxValue(vector<vector<int>>& g) {//1.创建dp表//2.初始化//3.填表//4.返回值int m = g.size(), n = g[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1));for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + g[i - 1][j - 1];return dp[m][n];}
};

    🦀🦀观看~~

相关文章:

DP学习第五篇之礼物的最大价值

DP学习第五篇之礼物的最大价值 剑指 Offer 47. 礼物的最大价值 - 力扣&#xff08;LeetCode&#xff09; 一.题目解析 二. 算法原理 状态表示 tips: 经验题目要求。以[i,j]位置为结尾&#xff0c;。。。 dp[i][j]: 到达[i, j]位置时&#xff0c;此时的最大礼物价值 状态转移…...

cURL error 1: Protocol “https“ not supported or disabled in libcurl

1、php项目composer update报错 2、curl -V检查 发现curl已经支持了https了 3、php版本检查 4、php插件检查 插件也已经含有openssl组件了 5、phpinfo检查 curl是否开启ssl 定位到问题所在&#xff0c;php7.4的 curl扩展不支持 https 需要重装 php7.4的curl扩展 6、curl下载 下…...

XCode升级后QT无法编译的问题

原因是SDK的版本变了&#xff0c;Qt配置的版本要修改。 解决办法如下&#xff1a; 1.找到 /Users/*/Qt/5.15.2/clang_64/mkspecsqdevice.pri 这个文件打开编辑&#xff0c; 在文件末尾追加一句 !host_build:QMAKE_MAC_SDKmacosx13.1 至于这个版本号13.1是怎么来的呢&#xff1…...

springboot编写mp4视频播放接口

简单粗暴方式 直接读取指定文件&#xff0c;用文件流读取视频文件&#xff0c;输出到响应中 GetMapping("/display1/{fileName}")public void displayMp41(HttpServletRequest request, HttpServletResponse response,PathVariable("fileName") String fi…...

华为OD机试真题 JavaScript 实现【机器人活动区域】【2023Q1 200分】,附详细解题思路

目录 一、题目描述二、输入描述三、输出描述四、解题思路五、JavaScript算法源码六、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 刷的越多&#xff0c;抽中的概率越大&#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测试&am…...

C++中的静态分配和动态分配

为什么不是 LaoJiaHelper mydalnew LaoJiaHelper (); 而是LaoJiaHelper mydal&#xff1f; 这个都没有new &#xff0c;对象为什么能用&#xff1f;在 C 中&#xff0c;有两种创建对象的方式&#xff1a;静态分配和动态分配。 静态分配&#xff1a; 当你使用类似 LaoJiaHelpe…...

【Android常见问题(五)】- Flutter项目性能优化

文章目录 知识回顾前言源码分析1. 渲染过程2. 分析工具3. 优化方法合理使用const关键词合理使用组件管理着色器编译垃圾 知识回顾 前言 项目迭代开发一定程度后&#xff0c;性能优化是重中之重&#xff0c;其中包括了包体积&#xff0c;UI 渲染、交互等多个方面。 通过 Flutt…...

JSON转换:实体类和JSONObject互转,List和JSONArray互转(fastjson版)

//1.java对象转化成String String sJSONObject.toJSONString(javaObject.class); //2. java对象转化成Object Object strJSONObject.toJSON(javaObject.class); //3.String类型转json对象 JSONObject jsonObject JSONObject.parseObject(str); //4. String…...

Java单例模式几种代码详解

在软件开发中&#xff0c;单例模式是一种常见的设计模式&#xff0c;它的目的是确保一个类在任何情况下都只有一个实例&#xff0c;同时提供一个全局访问点。在Java中&#xff0c;有几种常见的实现单例模式的方式&#xff0c;下面将逐一进行详细解释。 懒汉式&#xff08;非线…...

PHP代码审计--理论

提供资料&#xff1a; php 基础 : https://www.runoob.com/php/php-tutorial.html php是什么&#xff1f; PHP 是服务器端脚本语言。 首先在学习PHP前需要对HTML 和CSS有一定的认识 PHP 能做什么&#xff1f; PHP 可以生成动态页面内容PHP 可以创建、打开、读取、写入、关…...

在云服务器上,clone github时报Connection timed outexit code: 128

文章目录 问题解决方案 问题 在执行pip install安装依赖时&#xff0c;需要clone github代码&#xff0c;此时报了Connection timed out&exit code: 128错误&#xff0c;原因是访问超时了&#xff0c;此时需要使用代理 fatal: unable to access https://github.com/hugg…...

小型双轮差速底盘寻迹功能的实现

1. 功能说明 寻迹机器人是一种能够跟踪特定物体或线路的机器人。它们通常具有以下功能和特点&#xff1a; ① 传感器&#xff1a;寻迹机器人配备了用于感知环境的传感器&#xff0c;如摄像头、灰度传感器等。这些传感器可以探测地面上的标记、颜色、纹理或其他特定特征&#xf…...

第七篇:k8s集群使用helm3安装Prometheus Operator

安装Prometheus Operator 目前网上主要有两种安装方式&#xff0c;分别为&#xff1a;1. 使用kubectl基于manifest进行安装 2. 基于helm3进行安装。第一种方式比较繁琐&#xff0c;需要手动配置yaml文件&#xff0c;特别是需要配置pvc相关内容时&#xff0c;涉及到的yaml文件太…...

Chrome 75不支持保存成mhtml的解决方法

在Chrome 75之前&#xff0c;可以设置chrome://flags -> save as mhtml来保存网页为mhtml。 升级新版&#xff0c;发现无法另存为/保存网页为MHTML了。 在网上搜索无果后&#xff0c;只得从chromium项目的commits中查找&#xff0c;原来chrome搞了个"Chrome Flag Owner…...

工程监测振弦采集仪应用于岩土工程监测案例

振弦采集仪是一种用于测量地面或岩土中振动参数的仪器&#xff0c;可以对地基、土壤和岩体的性质及其变化进行监测。在岩土工程监测中&#xff0c;振弦传感器被广泛应用于测量土体或岩体的振动情况&#xff0c;以了解地震或其他自然灾害的影响。 以下是一个振弦采集仪应用岩土工…...

配置HDFS单机版,打造数据存储的强大解决方案

目录 简介&#xff1a;步骤&#xff1a;安装java下载安装hadoop配置hadoop-env.sh配置 core-site.xml配置hdfs-site.xml初始化hdfs文件系统启动hdfs服务验证hdfs 结论&#xff1a; 简介&#xff1a; Hadoop分布式文件系统&#xff08;HDFS&#xff09;是Hadoop生态系统中的一个…...

U盘删除的文件怎么找回?4个简单方法分享!

“在u盘里不小心删除的文件到底还能不能找回来呀&#xff1f;真的好着急啊&#xff01;这个u盘对我来说真的很重要&#xff0c;怎么恢复里面的数据呢&#xff1f;请各位大佬帮帮我吧&#xff01;” 作为一个便捷的存储工具&#xff0c;u盘逐渐获得大众的青睐。在互联网时代&…...

【雕爷学编程】MicroPython动手做(27)——物联网之掌控板小程序2

知识点&#xff1a;什么是掌控板&#xff1f; 掌控板是一块普及STEAM创客教育、人工智能教育、机器人编程教育的开源智能硬件。它集成ESP-32高性能双核芯片&#xff0c;支持WiFi和蓝牙双模通信&#xff0c;可作为物联网节点&#xff0c;实现物联网应用。同时掌控板上集成了OLED…...

形参动态内存开辟和柔性数组

//柔性数组 //定义&#xff1a;结构体最后一个成员允许是未知大小的数组 // 优点;在开辟空间时&#xff0c;连续开辟&#xff0c;便于释放空间&#xff0c;不会因多次开辟&#xff0c;导致释放空间出错 // 开辟空间时&#xff0c;节省动态开辟次数&#xff0c;节省空间&am…...

【LLM系列之指令微调】长话短说大模型指令微调的“Prompt”

1 指令微调数据集形式“花样”太多 大家有没有分析过 prompt对模型训练或者推理的影响&#xff1f;之前推理的时候&#xff0c;发现不加训练的时候prompt&#xff0c;直接输入模型性能会变差的&#xff0c;这个倒是可以理解。假如不加prompt直接训练&#xff0c;是不是测试的时…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...