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

[动态规划] (七) 路径问题:LCR 166.剑指offer 47. 珠宝的最高价值

[动态规划] (七) 路径问题:LCR 166./剑指offer 47. 珠宝的最高价值

文章目录

      • [动态规划] (七) 路径问题:LCR 166./剑指offer 47. 珠宝的最高价值
        • 题目解析
        • 解题思路
          • 状态表示
          • 状态转移方程
          • 初始化和填表顺序
        • 返回值
        • 代码实现
        • 总结

LCR 166. 珠宝的最高价值

image-20231105154428372

题目解析

(1) 二维矩阵中存放的是每个珠宝的价值

(2) 从左上角取到右下角

(3) 只能向右或者向下移动

解题思路

image-20231105165348213

状态表示

按照以往的经验:dp[i] [j] 以(i,j)位置为终点,得到的珠宝总价值。

状态转移方程

以状态表示可以得出:

dp(i,j)取决于两个位置的价值:dp(i-1,j)和dp(i, j-1)。

所以dp(i,j)就等于它们两个的最大值,再加上(i,j)位置对应的价值。

所以

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + (i,j)位置对应的价值
初始化和填表顺序
  • 初始化

image-20231105164738200

初始化时,只需要处理一下第一行和第一列的边界情况即可。

所以我们多开辟一列和一行(蓝色格子),又由于 dp(i,j)就等于它们两个的最大值,再加上(i,j)位置对应的价值。所以我们只需要将多开辟的初始化为0即可。我们在创建dp数组时,扩容后正好是0。

  • 填表顺序

一列一列填表即可。

返回值

多开辟一列和一行,返回dp[m] [n]即可。

看到这里,大家可以先尝试实现代码,再接下来看下面的内容。


代码实现
class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {//创建dp数组int m = frame.size(), n = frame[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1));//初始化// dp[1][1] = frame[0][0];//填表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];}
};

image-20231105165616179

总结

细节:多开辟一列一行,相当于我们将下标向右下方移动。所以最后在找原数组中对应位置,行和列下标应该都进行减1。如,frame[i-1] [j-1]

相关文章:

[动态规划] (七) 路径问题:LCR 166.剑指offer 47. 珠宝的最高价值

[动态规划] (七) 路径问题&#xff1a;LCR 166./剑指offer 47. 珠宝的最高价值 文章目录 [动态规划] (七) 路径问题&#xff1a;LCR 166./剑指offer 47. 珠宝的最高价值题目解析解题思路状态表示状态转移方程初始化和填表顺序 返回值代码实现总结 LCR 166. 珠宝的最高价值 题目…...

Mysql进阶-SQL优化篇

插入数据 insert 我们需要一次性往数据库表中插入多条记录&#xff0c;可以从以下三个方面进行优化。 批量插入数据 一条insert语句插入多个数据&#xff0c;但要注意&#xff0c;每个insert语句最好插入500-1000行数据&#xff0c;就得重新写另一条insert语句 Insert into…...

VueI18n中英文切换 vue2.0

1: npm install --save vue-i18n8.0.0 &#xff08;版本不要高了&#xff0c;不然报错&#xff09; 2&#xff1a;创建相关文件 3&#xff1a;main.js文件配置 //i18n插件 import VueI18n from vue-i18n // element-ui多语言文件 import locale from element-ui/lib/locale;…...

VUE组件间通信的七种方式

目录 1、 props / $emit &#xff08;1&#xff09;父组件向子组件传值&#xff08;props的用法&#xff09; &#xff08;2&#xff09;子组件向父组件传递数据&#xff08;$emit的用法&#xff09; 2、ref / $refs 用法&#xff1a; 3、eventBus事件总线&#xff08;$e…...

问chatgpt最近生活的困难

你知道吗&#xff0c;因为我做的所有的事情没有任何目的性&#xff0c;所以曾经过的很好&#xff0c;这种很好是一种逃避式的好&#xff0c;怎么说呢&#xff1f;遇到困难了&#xff0c;那就不做了&#xff0c;换下一个项目。比如打游戏&#xff0c;如果我这局玩王者荣耀&#…...

Flink源码解析八之任务调度和负载均衡

源码概览 jobmanager scheduler:这部分与 Flink 的任务调度有关。 CoLocationConstraint:这是一个约束类,用于确保某些算子的不同子任务在同一个 TaskManager 上运行。这通常用于状态共享或算子链的情况。CoLocationGroup & CoLocationGroupImpl:这些与 CoLocationCon…...

4.3 传送门

算法设计与分析 4.3 传送门 题目描述 现在有 n 个传送门&#xff0c;你处在第一个传送门的位置&#xff0c;第 i 个传送门可以将你传送到第 i-a[i] 到第 ia[i] 范围内的任意一个传送门&#xff0c;请问你最少需要几次操作&#xff0c;使得你可以传送到最后一个传送门的位置。 …...

NLP之Bert介绍和简单示例

文章目录 1. Bert 介绍2. 代码示例2.1 代码流程 1. Bert 介绍 2. 代码示例 from transformers import AutoTokenizertokenizer AutoTokenizer.from_pretrained("bert-base-chinese") input_ids tokenizer.encode(欢迎来到Bert世界, return_tensorstf) print(input…...

【Windows】Google和火狐浏览器禁用更新的操作方式

想必很多网民常用的浏览器是Edge&#xff0c;Google&#xff0c;火狐这三种&#xff0c;但是浏览器都有后台自动更新&#xff0c;更新提示会一直显示&#xff0c;要用户去点击才关掉&#xff0c;有点强迫症的用户就会想要把它一直关掉&#xff0c;可每次打开都关不掉&#xff0…...

关于编程不得不说的事

这些年&#xff0c;互联网爆炸式的发展&#xff0c;促生了无数程序员&#xff0c;也促生了大量 IT培训机构。短短数年间&#xff0c;科班出生的程序员和培训机构出生的程序员呈指数增长。程序员的职业也不再是金饭碗。写了这么多代码&#xff0c;有些感触&#xff0c;所以写下来…...

2.4G合封芯片 XL2422,集成M0核MCU,高性能 低功耗

XL2422芯片是一款高性能低功耗的SOC集成无线收发芯片&#xff0c;集成M0核MCU&#xff0c;工作在2.400~2.483GHz世界通用ISM频段。该芯片集成了射频接收器、射频发射器、频率综合器、GFSK调制器、GFSK解调器等功能模块&#xff0c;并且支持一对多线网和带ACK的通信模式。发射输…...

【QT基础入门 控件篇】QLineEdit 基础、高级和样式表使用详解

一、QLineEdit简介 QLineEdit是一个单行文本编辑器&#xff0c;它可以让用户输入和编辑纯文本&#xff0c;也可以设置一些有用的编辑功能&#xff0c;如撤销和重做、剪切和粘贴、拖放等。QLineEdit: 可以根据不同的回显模式&#xff08;echoMode&#xff09;来显示不同的输入内…...

网络安全(网络安全)小白自学

想自学网络安全&#xff08;黑客技术&#xff09;首先你得了解什么是网络安全&#xff01;什么是黑客&#xff01; 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全…...

dupeGuru 清理微信重复文件

本文摘录于&#xff1a;https://www.bilibili.com/video/BV13p4y1G75Y/?spm_id_from333.337.search-card.all.click&vd_source483e5c52353ea59d1a5eadac7737591a只是做学习备份之用&#xff0c;绝无抄袭之意&#xff0c;有疑惑请联系本人&#xff01; 微信用了七八年,文件…...

华为RS设备状态及接口配置命令

1、查看硬件信息 ①查看序列号 查看整机序列号 display esn display sn ②、查看功率 电源功率 display power 查看光模块功率 display transceiver interface gigabitethernet 1/0/0 verbose ③、查看风扇 display fan ④、查看温度 display temperature all ⑤、查看硬…...

单链表的应用(2)

环形链表的约瑟夫问题 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数&#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后&#xff0c;只剩下一个人&#xff0c;问最后留下的这个人编号是多少&#xff1f; 利用链表实现 思路&#xff1…...

【Boost | C++】使用Boost库创建文件夹

#include <boost/filesystem.hpp> #include <iostream> bool CreateDirectory(const std::string &dir_path) {try {if (...

月报总结|Moonbeam 10月份大事一览

万圣节快乐&#xff01;时间一晃眼&#xff0c;10月已经迈入尾声&#xff0c;也即将迎来寒冷的冬天。但与季节相反&#xff0c;加密产业近期的发展可以说是高潮起伏&#xff0c;热度不断攀升。Moonbeam在10月中也发布了许多重大的更新&#xff0c;如Uniswap V3前段上线、众贷DO…...

Latex安装记录

Title:Latex 基本概念 Tex:是一种具有编译和排版功能的基础语言&#xff0c;相当于C语言。 Latex:&#xff1a;LaTex是 Tex 的扩展版本&#xff0c;拥有多种宏包&#xff0c;能实现比 Tex 更多的功能。 TexLive&#xff1a;是一种 Tex 语言的发行版本。 Texstudio: 一种软件相…...

JavaEE-博客系统2(功能设计)

本部分内容&#xff1a;实现博客列表页&#xff1b;web程序问题的分析方法&#xff1b;实现博客详情页&#xff1b; 该部分的代码如下&#xff1a; WebServlet("/blog") public class BlogServlet extends HttpServlet {//Jackson ObjectMapper类(com.fasterxml.jac…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7

在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤&#xff1a; 第一步&#xff1a; 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为&#xff1a; // 改为 v…...

Cursor AI 账号纯净度维护与高效注册指南

Cursor AI 账号纯净度维护与高效注册指南&#xff1a;解决限制问题的实战方案 风车无限免费邮箱系统网页端使用说明|快速获取邮箱|cursor|windsurf|augment 问题背景 在成功解决 Cursor 环境配置问题后&#xff0c;许多开发者仍面临账号纯净度不足导致的限制问题。无论使用 16…...

Vue 实例的数据对象详解

Vue 实例的数据对象详解 在 Vue 中,数据对象是响应式系统的核心,也是组件状态的载体。理解数据对象的原理和使用方式是成为 Vue 专家的关键一步。我将从多个维度深入剖析 Vue 实例的数据对象。 一、数据对象的定义方式 1. Options API 中的定义 在 Options API 中,使用 …...

[特殊字符] Spring Boot底层原理深度解析与高级面试题精析

一、Spring Boot底层原理详解 Spring Boot的核心设计哲学是约定优于配置和自动装配&#xff0c;通过简化传统Spring应用的初始化和配置流程&#xff0c;显著提升开发效率。其底层原理可拆解为以下核心机制&#xff1a; 自动装配&#xff08;Auto-Configuration&#xff09; 核…...

触发DMA传输错误中断问题排查

在STM32项目中&#xff0c;集成BLE模块后触发DMA传输错误中断&#xff08;DMA2_Stream1_IRQHandler进入错误流程&#xff09;&#xff0c;但单独运行BLE模块时正常&#xff0c;表明问题可能源于原有线程与BLE模块的交互冲突。以下是逐步排查与解决方案&#xff1a; 一、问题根源…...