leetcode做题笔记213. 打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 1:
输入:nums = [2,3,2] 输出:3 解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入:nums = [1,2,3,1] 输出:4 解释:你可以先偷窃 1 号房屋(金额 = 1),然后偷窃 3 号房屋(金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 3:
输入:nums = [1,2,3] 输出:3
思路一:动态规划
c解法
int rob(int* nums, int numsSize){int dp[numsSize];if (numsSize == 0) return 0;if(numsSize==1)return nums[0];if(numsSize==2)return fmax(nums[0],nums[1]);int i, a[numsSize], b[numsSize];a[0] = nums[0];a[1] = nums[0];b[0] = 0;b[1] = nums[1];for(i = 2; i < numsSize; i++) {a[i] = fmax(a[i-1], a[i-2] + nums[i]);b[i] = fmax(b[i-1], b[i-2] + nums[i]);}return fmax(a[numsSize-2], b[numsSize-1]);}
分析:
本题为动态规划经典问题之一:打家劫舍,找出状态方程a[i] = fmax(a[i-1], a[i-2] + nums[i]);因为不能偷相邻房屋,所以偷的金额最大有两种可能:从第一个开始和第二个开始,分别计算两种情况的最大金额再比较两个金额即可得到答案
总结:
本题考察动态规划的应用,分别考虑从第一和第二个开始的情况即可解决
相关文章:
leetcode做题笔记213. 打家劫舍 II
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一…...
多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测
多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络…...
玻色量子签约移动云“五岳”量子云计算创新加速计划!
2023年4月24-26日,由中国移动通信集团主办的“云擎未来 智信天下”2023移动云大会在苏州圆满落幕。 中国移动在本次大会发布了“五岳”量子云计算创新加速计划。作为中国移动量子计算方向的战略伙伴,玻色量子创始人&CEO文凯博士代表北京玻色量子科技…...
Postgresql在linux环境下以源码方式安装
linux环境下源码方式的安装 1.下载安装包(源码安装方式) 安装包下载 https://www.postgresql.org/ftp/source/ 2.安装postgresql ① 创建安装目录 mkdir /opt/pgsql12② 解压下载的安装包 cd /opt/pgsql12 tar -zxvf postgresql-12.16.tar.gz ③编…...
vivo发布“蓝心千询”自然语言对话机器人
🦉 AI新闻 🚀 vivo发布“蓝心千询”自然语言对话机器人 摘要:vivo今日发布了“蓝心千询”自然语言对话机器人,基于蓝心大模型。蓝心千询可以进行知识信息的快速问答,文学创作、图片生成,甚至还能编写程序…...
Python基础入门例程39-NP39 字符串之间的比较(运算符)
最近的博文: Python基础入门例程38-NP38 牛牛的逻辑运算(运算符)-CSDN博客 Python基础入门例程37-NP37 不低于与不超过(运算符)-CSDN博客 Python基础入门例程36-NP36 谁的数字大(运算符)-CSD…...
java中的Thread类解析
实现线程的三种方式 1、继承Thread类,重写里面的run方法 public class MyThread extends Thread{Overridepublic void run() {System.out.println("threadName:"Thread.currentThread().getName());}}/*** 方式一:继承Thread类,重…...
如何正确清理DNS缓存
前言 有些场景,需要刷新自己本机的DNS缓存,比如说某个cdn访问不到,某个网络不通等等,都有可能是由于DNS缓存记录了错误的ip映射关系而导致的。本文介绍下如何刷新本机的DNS缓存。 Mac 如果你是mac用户,执行以下操作…...
Git从基础到实践
1.Git是用来做什么的? git就是一款版本控制软件,主要面向代码的管理。你可以理解为Git是一个代码的备份器,给你的每一次修改后的代码做个备份,防止丢失,这个是git最基本的功能。 其次,git不止备份,当你需要比对多…...
C 保留字解释
语句 // 单行注释 /* */ 多行注释 #include 头文件引入声明 #define 预先定义 return 结果返回语句(可以带参数,也可不带参数) printf(); 输出 if 条件语句 else 条件语句否定分支(和 if 连用&a…...
【Web】https 与 http 的区别
文章目录 一、基本概念二、区别对比 一、基本概念 http :超文本传输协议,一种网络传输协议,一个客户端和服务器请求和应答的标准(TCP)。 https :简单讲就是在http基础上 使用 SSL 或 TLS 对请求和响应进行…...
【KVM】半虚拟化和全虚拟化技术
前言 大家好,我是秋意零。 上一篇的介绍了软件和硬件虚拟化类型,现在来看看半虚拟化技术和通过硬件虚拟化类型辅助的全虚拟化技术吧! 👿 简介 🏠 个人主页: 秋意零🔥 账号:全平台…...
react中的useReducer复杂的状态管理
一、useReducer reducer官网教程 useReducer 是 React 提供的一个用于状态管理的 Hook。它可以替代 useState,更适用于处理复杂的状态逻辑。 useReducer 接受一个reducer函数和一个初始状态,并返回当前状态以及一个 dispatch 函数,用来触发…...
SpringCloudAlibaba - 项目完整搭建(Nacos + OpenFeign + Getway + Sentinel)
目录 一、SpringCloudAlibaba 项目完整搭建 1.1、初始化项目 1.1.1、创建工程 1.1.2、配置父工程的 pom.xml 1.1.3、创建子模块 1.2、user 微服务 1.2.1、配置 pom.xml 1.2.2、创建 application.yml 配置文件 1.2.3、创建启动类 1.2.4、测试 1.3、product 微服务 1…...
如何使用Python的matplotlib和seaborn库绘制颜色渐变的高级散点图
前言 我的科研论文中需要绘制一个精美的散点图,表达的是各个散点距离中心点的距离远近情况,特点如下: 绘图的美观程度高根据距离目标点的距离的不同,各个散点能有颜色或者是透明度上的区分相应的统计量是与中心点(目…...
根据Word模板,使用POI生成文档
突然想起来有个小作业:需要根据提供的Word模板填充数据。这里使用POI写了一个小demo验证下。 测试用模板: 执行结果 1.引入依赖坐标 <dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxml</artifactId&…...
大语言模型的学习路线和开源模型的学习材料《一》
文章目录 第一层 LLMs to Natural Language Processing (NLP)第一重 ChatGLM-6B 系列ChatGLM3ChatGLM2-6BChatGLM-6B第十重 BaichuanBaichuan2Baichuan-13Bbaichuan-7B第十一重 Llama2第二重 Stanford Alpaca 7B第三重 Chinese-LLaMA-Alpaca第四重 小羊驼 Vicuna第五重 MOSS第六…...
【案例】3D地球
效果图: 直接放源码 <!DOCTYPE html> <html> <head><meta http-equiv"Content-Type" content"text/html; charsetutf-8" /><meta name"viewport" content"initial-scale1.0, user-scalableno" …...
安全组问题 访问华为云服务器端口
一些常用的安全组的配置示例,包括远程登录云服务器,对外提供网站访问、不同安全组内实例内网互通等。 通常情况下,安全组默认拒绝所有来自外部的请求。您需要遵循白名单原则添加安全组入方向规则,允许来自外部的特定请求访问安全组…...
音视频常见问题(七):首开慢
本文主要讨论音视频应用中的首开慢问题,文章介绍了首开慢的产生原因:DNS解析耗时、网络传输协议耗时、传输网络调度耗时,并提供了排查方式和解决方案。即构科技的Express SDK和MSDN网络可以有效的解决首开慢问题,且节省开发成本。…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
