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

动态规划:07.路径问题_珠宝的最大价值_C++

题目链接:LCR 166. 珠宝的最高价值 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/

一、题目解析

题目:

解析:

有过做前几道题的经验,我们会发现这道题其实就是最短路径问题,只不过变成了最“长”路径,我们有多种方式到达右下角,但是我们要求到达=右下角的同时,珠宝价值也最大

二、算法原理

1、状态表示

我们在状态标识的时候,一般都会创建一个数组dp,也就是我们所说的dp表,我们要做的就是把每一个状态的值填入这个表内,最终这个表内的某一个值可能就是我们要返回的值。 

  状态简单理解就是dp表内某一个值代表的含义。

如何确定状态表示

  • 题目要求

   简单的题目里一般会给出

  • 经验+题目要求

  越学越深入,动态规划也是熟能生巧,在题目中没有明显给出的时候,我们就要凭借自己做题的经验来确定,所以就需要我们大量的做题。

  • 分析问题的过程中,发现重复子问题

 分析问题的过程中把重复子问题抽象成我们的状态表示,这个更难理解,一切的基础都是我们先对动态规划算法熟练运用。我也不懂,我们慢慢来。

综上:我们通常会以一个位置为结尾或者开始求得我们想要的答案

那我们的这道题得状态表示是什么样的:

根据经验:我们以为一个位置为结尾做题

dp[i][j]状态表示:到达位置(i,j)时,珠宝价值最大

2、状态转移方程

 确定状态表示之后我们就可以根据状态标识推出状态转移方程

  状态转移方程是什么?

不讲什么复杂的,简单来说状态转移方程就是    dp[i][j]等于什么 dp[i][j]=?

  这个就是状态转移方程,我们要做的,就是推出dp[i][j]等于什么

  我们根据状态表示再结合题目+经验去推理转移方程,这一步也是我们整个解题过程中最难的一步

  我们在这道题先简单了解下什么是状态转移方程,之后比较难的题目再细推

  我们知道,我们每次直能向下或者向右走,此时dp表示到达(i,j)该位置时珠宝价值达到最大,那么就是我们向下或者向右到达(i,j)位置后价值达到最大,既然要求最大,(i,j)位置的价值也不会影响,那我们就要要求到达(i-1,j)或者(i,j-1)的珠宝价值达到最大,并且只能选其中最大的那一个

我们再画图可以看出,我们选出到达(i,j)位置之前的最大价值dp[i-1][j]或者dp[i][j-1],再加上本身价值,就是到达(i,j)位置的最大价值

状态转移方程:dp[i][j]=max(dp[i-1][j],dp[i][j-1])+(i,j)的本身价值

3、初始化

 我们创建dp表就是为了把他填满,我们初始化是为了防止在填表的过程中越界

怎么谈越界?

  比如我们在求dp[0][0]时,我们就需要知道dp[-1][0]或者dp[0][-1]的值,但是我们没有这两个位置,就会造成越界。

 不仅仅是第一个位置,我们的第一行和第一列,都存在所要位置的价值最大值不存在问题

 所以我们在创建dp表时,我们需要额外增加一行一列,这样我们的越界问题就解决了

 另外,我们为了让新增的行列元素值不影响填表,我们应该把他们初始化为0

  

4、填表顺序

从左到右,从上到下依次填表,这样能保证我们填表时其它的值都有

5、返回值

返回dp表右下角的值

三、编写代码

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m=frame.size(),n=frame[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])+frame[i-1][j-1];}}return dp[m][n];}
};

相关文章:

动态规划:07.路径问题_珠宝的最大价值_C++

题目链接&#xff1a;LCR 166. 珠宝的最高价值 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/ 一、题目解析 题目&#xff1a; 解析&#xff1a; 有过做前几道题的经验&#xff0c;我们会发现这道题其实就…...

COMDEL电源CX2500S RF13.56MHZ RF GENERATOR手侧

COMDEL电源CX2500S RF13.56MHZ RF GENERATOR手侧...

GPU加速生物信息分析的尝试

GPU工具分类 实话实说&#xff0c;暂时只有英伟达的GPU才能实现比较方便的基因组分析集成化解决方案&#xff0c;其他卡还需要努力呀&#xff0c;或者需要商业公司或学术团体的努力开发呀&#xff01;FPGA等这种专用卡的解决方案也是有的&#xff0c;比如某测序仪厂家&#xf…...

【零散技术】详解Odoo17邮件发送(一)

序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo的邮件功能十分强大&#xff0c;在非常多的场景中可以看见其应用&#xff0c;例如原生的用户邀请&#xff0c;报价单发送&#xff0c;询价单发送等等.... 那么抛开原生自带的功能&#xff0c;我们如何巧妙的通过代码进行自…...

函数题 6-5 求自定类型元素的最大值【PAT】

文章目录 题目函数接口定义裁判测试程序样例输入样例输出样例 题解解题思路完整代码AC代码 编程练习题目集目录 题目 要求实现一个函数&#xff0c;求N个集合元素S[]中的最大值&#xff0c;其中集合元素的类型为自定义的ElementType。 函数接口定义 ElementType Max( Element…...

Python---爬虫

文章目录 目录 前言 一.Http请求/响应模块 requests模块 二.文本筛选模块 re模块 XPath模块 XPath 路径表达式 XPath 语法元素 三. 爬虫模板 爬虫案例 前言 Python爬虫是一种通过自动化程序爬取互联网上的信息的技术。爬虫可以自动访问网页并提取所需的数据&#xff0c;比…...

设计模式之组合设计模式

一、组合设计模式概念 组合模式 (Component) 是一种结构型设计模式&#xff0c;将对象组合成树形结构以表示“部分-整体”的层次结构。 组合模式使得用户对单个对象和组合对象的使用具有唯一性。 适用场景 想要表示对象的部分-整体层次结构。想要客户端忽略组合对象与单个对象的…...

Java汽车销售管理

技术架构&#xff1a; springboot mybatis Mysql5.7 vue2 npm node 有需要该项目的小伙伴可以添加我Q&#xff1a;598748873&#xff0c;备注&#xff1a;CSDN 功能描述&#xff1a; 针对汽车销售提供客户信息、车辆信息、订单信息、销售人员管理、财务报表等功能&…...

js TypeError: Cannot read property ‘initialize’ of undefined

js TypeError: Cannot read property ‘initialize’ of undefined 在JavaScript开发旅程中&#xff0c;遇到TypeError: Cannot read property ‘initialize’ of undefined这样的错误提示&#xff0c;无疑是令人沮丧的。这个错误通常意味着你试图访问一个未定义对象的initiali…...

【Motion Forecasting】【摘要阅读】BANet: Motion Forecasting with Boundary Aware Network

BANet: Motion Forecasting with Boundary Aware Network 这项工作发布于2022年&#xff0c;作者团队来自于OPPO。这项工作一直被放在arxiv上&#xff0c;并没有被正式发表&#xff0c;所提出的方法BANet在2022年达到了Argoverse 2 test dataset上的SOTA水准。 Method BANet…...

Cpp快速入门语法(下)(2)

文章目录 前言一、函数重载概念与使用C为何支持函数重载&#xff1f; 二、引用概念语法特性权限(常引用)使用场景与指针的区别 三、内联函数四、auto关键字(C11)五、基于范围的for循环(C11)六、指针空值nullptr(C11)总结 前言 承前启后&#xff0c;正文开始&#xff01; 一、函…...

【GO开发】MacOS上搭建GO的基础环境-Hello World

文章目录 一、引言二、安装Go语言三、配置环境变量&#xff08;可跳过&#xff09;四、Hello World五、总结 一、引言 Go语言&#xff08;Golang&#xff09;因其简洁、高效、并发性强等特点&#xff0c;受到了越来越多开发者的喜爱。本文将带你一步步在Mac操作系统上搭建Go语…...

探索轻量级语言模型 GPT-4O-mini 的无限可能

随着人工智能技术的日益发展&#xff0c;语言模型正逐渐成为人们日常生活和工作中不可或缺的一部分。其中&#xff0c;GPT-4O-mini 作为一个轻量级大模型&#xff0c;以其强大的功能和易用性吸引了众多关注。本文将带您了解 GPT-4O-mini 的出色表现、应用场景以及如何免费使用这…...

CSS 笔记 1

1. CSS 优先级&#xff0c; 内部大于外部。 2. 几个属性&#xff1a; flex-grow: 1; 让 当前元素 在剩余空间中&#xff0c; 占据尽可能多的高度&#xff0c;确保它能在中间居中。 max-height: 300px; 限制最大高度 300 像素&#xff0c; flex-grow: 1; 导致占的太满了&#x…...

2024/9/16 dataloader、tensorboard、transform

一、pytorch两大法宝元素 假设有一个名为pytorch的包 dir()&#xff1a;用于打开包&#xff0c;看里面的内容 help():用于查看具体的内容的用处 二、python文件&#xff0c;python控制台和jupyter的使用对比 三、pytorch读取数据 pytorch读取数据主要涉及到两个类&#xff1…...

C/C++语言基础--从C到C++的不同(下),15个部分说明C与C++的不同

本专栏目的 更新C/C的基础语法&#xff0c;包括C的一些新特性 前言 1-10在上篇C/C语言基础–从C到C的不同(上&#xff09;&#xff1b;当然C和C的不同还有很多&#xff0c;本人暂时只总结这些&#xff0c;其他的慢慢更新&#xff1b;上一篇C/C语言基础–从C到C的不同(上&…...

物理感知扩散的 3D 分子生成模型 - PIDiff 评测

PIDiff 是一个针对蛋白质口袋特异性的、物理感知扩散的 3D 分子生成模型&#xff0c;通过考虑蛋白质-配体结合的物理化学原理来生成分子&#xff0c;在原理上&#xff0c;生成的分子可以实现蛋白-小分子的自由能最小。 一、背景介绍 PIDiff 来源于延世大学计算机科学系的 Sang…...

蓝桥杯-基于STM32G432RBT6的LCD进阶(LCD界面切换以及高亮显示界面)

目录 一、页面切换内容详解 1.逻辑解释 2.代码详解 code.c&#xff08;内含详细讲解&#xff09; code.h main.c 3.效果图片展示 ​编辑 二、页面选项高亮内容详解 1.逻辑解释 2.读入数据 FIRST.第一种高亮类型 code.c&#xff08;内含代码详解&#xff09; code.…...

2022高教社杯全国大学生数学建模竞赛C题 问题一(1) Python代码

目录 问题 11.1 对这些玻璃文物的表面风化与其玻璃类型、纹饰和颜色的关系进行分析数据探索 -- 单个分类变量的绘图树形图条形图扇形图雷达图 Cramer’s V 相关分析统计检验列联表分析卡方检验Fisher检验 绘图堆积条形图分组条形图 分类模型Logistic回归随机森林 import matplo…...

【3D打印】3D打印机运动控制“Gcode”

一、Gcode是什么&#xff1f; Gcode是一种用于控制数控机床&#xff08;包括3D打印机&#xff09;的语言。它由一系列指令组成&#xff0c;每个指令控制机器的一个特定动作。 二、基础术语 G指令&#xff1a;用于控制机器的运动。M指令&#xff1a;用于控制机器的其他功能&a…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案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…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...