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

[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍

[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍

文章目录

      • [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍
        • 题目分析
        • 题目解析
          • 状态表示
          • 状态转移方程
          • 初始化和填表顺序
        • 代码实现
          • 按摩师
          • 打家劫舍
        • 总结

注:本题与打家劫舍基本一样,所以只写一道按摩师,末尾只会加上打家劫舍1的代码。

面试题 17.16. 按摩师
198. 打家劫舍
image-20231107161334755

题目分析

(1) 按摩师不能连续接预约

(2) 按摩师可以选择接或者不接预约

(3) 返回预约时间最长的分钟数

题目解析
状态表示

dp[i]:按往常的经验,以i为结尾的最大的服务的分钟数

dp[i]又可以分为:

  • f[i]:到i位置,i次预约的服务的最大分钟数
  • g[i]:到i位置,不接i次预约的服务的最大分钟数
状态转移方程
  • f[i]:

f[i]是到i位置,必须接i位置的服务的最大分钟数。

由于不能连续接受服务,所以接了i位置,i-1位置就不能接受预约了。

g[i-1]正好是到i-1位置且不接受i-1预约的最大分钟数,再加上对应的i位置的分钟数就是f[i]。(可以参考后面的图)

f[i] = g[i-1] + nums[i]
  • g[i]:

g[i]是到i位置,不接i位置的服务的最大分钟数。

由于不接i位置,所以只能看i-1位置。而i-1位置也分为接或者不接。

i-1位置为f[i-1] (参考状态表示),不接i-1为g[i-1] (参考状态表示)。

由于求最大值,取它们两个较大的值即可。(可以参考后面的图)

g[i] = max(f[i-1], g[i-1])

image-20231107164235791

初始化和填表顺序
  • 初始化
  • 访问i-1,所以一般初始化前面的位置。

i == 0时,参考状态表示

f[0] = nums[0], g[0] = 0
  • 填表顺序

从左向右填表。

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


代码实现
按摩师
class Solution {
public:int massage(vector<int>& nums) {//创建dp数组int n = nums.size();if(n == 0) return 0;vector<int> f(n);//选到i位置,必选ivector<int> g(n);//选到i位置,不选i//初始化f[0] = nums[0], g[0] = 0;//填表for(int i = 1; i < n; i++){g[i] = max(f[i-1], g[i-1]);f[i] = g[i-1] + nums[i];}//返回值return max(g[n-1], f[n-1]);}
};

image-20231107163822064

打家劫舍
class Solution {
public:int rob(vector<int>& nums) {//创建dp数组int n = nums.size();vector<int> f(n);vector<int> g(n);//初始化f[0] = nums[0], g[0] = 0;//填表for(int i = 1; i < n; i++){f[i] = g[i-1] + nums[i];g[i] = max(g[i-1], f[i-1]);}//返回值return max(f[n-1], g[n-1]);}
};

image-20231107163851645

总结

细节:注重将问题细分,加上画图理解即可。

相关文章:

[动态规划] (十一) 简单多状态 LeetCode 面试题17.16.按摩师 和 198.打家劫舍

[动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍 文章目录 [动态规划] (十一) 简单多状态: LeetCode 面试题17.16.按摩师 和 198.打家劫舍题目分析题目解析状态表示状态转移方程初始化和填表顺序 代码实现按摩师打家劫舍 总结 注&#xff1a;本题与…...

【EI会议投稿】第三届计算机、人工智能与控制工程国际学术会议 (CAICE 2024)

The 3rd International Conference on Computer, Artificial Intelligence and Control Engineering (CAICE 2024) 第三届计算机、人工智能与控制工程国际学术会议 第三届计算机、人工智能与控制工程国际学术会议&#xff08;CAICE 2024&#xff09;将于2024年1月26-28日在西…...

python 之 列表推导式

文章目录 基本结构示例 1&#xff1a;将列表中的元素乘以 2 添加条件判断示例 2&#xff1a;筛选出偶数并加倍 嵌套列表推导式示例 3&#xff1a;生成九九乘法表 使用条件表达式示例 4&#xff1a;根据条件返回不同的值 镶嵌使用详细介绍基本结构示例生成二维数组多重筛选和操作…...

【左程云算法全讲2】链表、栈、队列、递归、哈希表和有序表

系列综述&#xff1a; &#x1f49e;目的&#xff1a;本系列是个人整理为了秋招面试的&#xff0c;整理期间苛求每个知识点&#xff0c;平衡理解简易度与深入程度。 &#x1f970;来源&#xff1a;材料主要源于左程云算法课程进行的&#xff0c;每个知识点的修正和深入主要参考…...

SQL第三次上机作业

1.查询与王利就读同一专业学生的借书证号和姓名 SELECT Lno,Rname FROM Reader WHERE Dept(SELECT DeptFROM ReaderWHERE Rname王利)2.查询比希望出版社出版的所有图书价格都高的图书信息 SELECT * FROM Book WHERE Price>(SELECT MAX(Price)FROM BookWHERE Press希望出版…...

前端事件案例补充

目录 定时器示例 搜索框示例 省市联动 定时器示例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><meta name"viewport" content"widthdevice-width, init…...

3.8 Android eBPF HelloWorld调试(二)

写在前面 我们开发eBPF程序的初衷就是再不改动内核的情况下,将内核监控数据传递给到用户态;像应用进程开发一样开发内核监控程序。 Android开机的时候eBPF程序被加载器加载到内核中,但此时它并没有被附加到内核函数上去,也就是ebpf程序并不会执行,我们可以理解为,它仅仅被…...

xss如何快速提取cookies

<script>alert(111)</script> <img srcx onerroralert(document.cookie)>测试一下baidu的xss <script>alert(111)</script><img srcx οnerrοralert(document.cookie)>...

在 ASP.NET C# 中用Aspose.PDF将 PDF 页面转换为 JPG 图像

PDF 是一种通用格式&#xff0c;通常用于打印和共享文档。 &#xff08;一&#xff09;C# PDF to JPG Converter API - 免费下载 Aspose.PDF for .NET是一个强大的 PDF 操作 API&#xff0c;可让您在 .NET 应用程序中创建和处理 PDF 文件。此外&#xff0c;它还允许您将 PDF 文…...

Docker Compose安装milvus向量数据库单机版-milvus基本操作

目录 安装Ubuntu 22.04 LTS在power shell启动milvus容器安装docker desktop下载yaml文件启动milvus容器Milvus管理软件Attu python连接milvus配置下载wget示例导入必要的模块和类与Milvus数据库建立连接创建名为"hello_milvus"的Milvus数据表插入数据创建索引基于向量…...

极致性能优化:前端SSR渲染利器Qwik.js | 京东云技术团队

引言 前端性能已成为网站和应用成功的关键要素之一。用户期望快速加载的页面和流畅的交互&#xff0c;而前端框架的选择对于实现这些目标至关重要。然而&#xff0c;传统的前端框架在某些情况下可能面临性能挑战且存在技术壁垒。 在这个充满挑战的背景下&#xff0c;我们引入…...

ES6~ES13新特性(二)

文章目录 一、ES71.Array Includes2.指数exponentiation运算符 二、ES81.Object values2.Object entries3.String Padding4.Trailing Commas5.Object Descriptors 三、ES9四、ES101.flat flatMap2.Object fromEntries3.trimStart、trimEnd4.其他知识点 五、ES111.BigInt2.Nulli…...

soildwork2022怎么样添加螺纹孔?

1.退出草图模式&#xff0c;点击需要添加螺纹孔的物体面&#xff0c;选中“特征”中的“异形孔向导” 2.选中“孔类型”为“直螺纹孔”&#xff0c;“标准”&#xff0c;“类型”&#xff0c;“孔规格”终止条件等。 3.设置完之后选择“位置” 4.鼠标左键在物体面上点一下&…...

【t5 pytorch版源码学习】t5-pegasus-pytorch源码学习

0. 项目来源 中文生成式预训练模型&#xff0c;以mT5为基础架构和初始权重&#xff0c;通过类似PEGASUS的方式进行预训练。 bert4keras版&#xff1a;t5-pegasus pytorch版&#xff1a;t5-pegasus-pytorch 本次主要学习pytorch版的代码解读。 项目结构&#xff1a; train…...

【springboot】spring的Aop结合Redis实现对短信接口的限流

前言 场景: 为了限制短信验证码接口的访问次数&#xff0c;防止被刷&#xff0c;结合Aop和redis根据用户ip对用户限流 1.准备工作 首先我们创建一个 Spring Boot 工程&#xff0c;引入 Web 和 Redis 依赖&#xff0c;同时考虑到接口限流一般是通过注解来标记&#xff0c;而注解…...

【MedusaSTears】怎么禁用edge浏览器截图功能?

版本 Microsoft Edge 版本 119.0.2151.44 (正式版本) (64 位) Ctrl Shift S 竟然是浏览器的截屏? 特么的啥时候多了这么个快捷键? 然后还没办法禁用,真TMD傻哔 edge://settings/accessibility解决方式: 参考资料: 怎么禁用edge浏览器截图功能&#xff1f; 您好&#x…...

【计算机网络】(谢希仁第八版)第三章课后习题答案

第三章 1.数据链路(即逻辑链路)与链路(即物理链路)有何区别? “电路接通了”与”数据链路接通了”的区别何在? 答&#xff1a;数据链路与链路的区别在于数据链路出链路外&#xff0c;还必须有一些必要的规程来控制数据的传输&#xff0c;因此&#xff0c;数据链路比链路多了…...

批量异步任务处理

当我们在项目中遇到很多业务同时处理&#xff0c;如果是串行肯定是影响性能的&#xff0c;这时候就需要异步执行了&#xff0c;说道异步肯定就有很多方案了 方案一&#xff1a; 比如使用spring的异步注解&#xff0c;比如下面的代码,每个方法上面都是异步注解&#xff0c;当时…...

宜昌市公安局、点军区政府与中科升哲达成战略合作,共建视频图像联合创新实验室

11月3日&#xff0c;宜昌视频图像联合创新战略合作签约仪式在宜昌市公安局举行。 宜昌市副市长、市公安局党委书记、局长上官福令&#xff0c;市公安局党委副书记、副局长龚海波&#xff0c;宜昌市点军区委书记万红&#xff0c;点军区委副书记、区长黄文云&#xff0c;升哲科技…...

java版小程序商城免费搭建-直播商城平台规划及常见的营销模式有哪些?电商源码/小程序/三级分销

1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

五、jmeter脚本参数化

目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...

EEG-fNIRS联合成像在跨频率耦合研究中的创新应用

摘要 神经影像技术对医学科学产生了深远的影响&#xff0c;推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下&#xff0c;基于神经血管耦合现象的多模态神经影像方法&#xff0c;通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里&#xff0c;本研…...

React、Git、计网、发展趋势等内容——前端面试宝典(字节、小红书和美团)

React React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么&#xff0c;Fiber架构&#xff0c;面试向面试官介绍&#xff0c;详细解释 用户: React Hook实现架构、.Hook不能在循环嵌套语句中使用 , 为什么&#xff0c;Fiber架构&#xff0c;面试向面试官介绍&#x…...

华硕电脑,全新的超频方式,无需进入BIOS

想要追求更佳性能释放 或探索更多可玩性的小伙伴&#xff0c; 可能会需要为你的电脑超频。 但我们常用的不论是BIOS里的超频&#xff0c; 还是Armoury Crate奥创智控中心超频&#xff0c; 每次调节都要重启&#xff0c;有点麻烦。 TurboV Core 全新的超频方案来了 4不规…...

LangChain + LangSmith + DeepSeek 入门实战:构建代码生成助手

本文基于 Jupyter Notebook 实践代码&#xff0c;结合 LangChain、LangSmith 和 DeepSeek 大模型&#xff0c;手把手演示如何构建一个代码生成助手&#xff0c;并实现全流程追踪与优化。 一、环境准备与配置 1. 安装依赖 pip install langchain langchain_openai2. 设置环境变…...

unipp---HarmonyOS 应用开发实战

HarmonyOS 应用开发实战指南 1. 开篇&#xff1a;为什么选择 HarmonyOS&#xff1f; 最近在开发鸿蒙应用时&#xff0c;发现很多开发者都在问&#xff1a;为什么要选择 HarmonyOS&#xff1f;这里分享一下我的看法&#xff1a; 生态优势 华为手机用户基数大&#xff0c;市场潜…...