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

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

你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#xff0c;相邻的房屋装有相互连通的防盗系统&#xff0c;如果两间相邻的房屋在同一…...

多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测

多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测 目录 多输入多输出 | Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 Matlab实现WOA-RBF鲸鱼算法优化径向基神经网络…...

玻色量子签约移动云“五岳”量子云计算创新加速计划!

2023年4月24-26日&#xff0c;由中国移动通信集团主办的“云擎未来 智信天下”2023移动云大会在苏州圆满落幕。 中国移动在本次大会发布了“五岳”量子云计算创新加速计划。作为中国移动量子计算方向的战略伙伴&#xff0c;玻色量子创始人&CEO文凯博士代表北京玻色量子科技…...

Postgresql在linux环境下以源码方式安装

linux环境下源码方式的安装 1.下载安装包&#xff08;源码安装方式&#xff09; 安装包下载 https://www.postgresql.org/ftp/source/ 2.安装postgresql ① 创建安装目录 mkdir /opt/pgsql12② 解压下载的安装包 cd /opt/pgsql12 tar -zxvf postgresql-12.16.tar.gz ③编…...

vivo发布“蓝心千询”自然语言对话机器人

&#x1f989; AI新闻 &#x1f680; vivo发布“蓝心千询”自然语言对话机器人 摘要&#xff1a;vivo今日发布了“蓝心千询”自然语言对话机器人&#xff0c;基于蓝心大模型。蓝心千询可以进行知识信息的快速问答&#xff0c;文学创作、图片生成&#xff0c;甚至还能编写程序…...

Python基础入门例程39-NP39 字符串之间的比较(运算符)

最近的博文&#xff1a; Python基础入门例程38-NP38 牛牛的逻辑运算&#xff08;运算符&#xff09;-CSDN博客 Python基础入门例程37-NP37 不低于与不超过&#xff08;运算符&#xff09;-CSDN博客 Python基础入门例程36-NP36 谁的数字大&#xff08;运算符&#xff09;-CSD…...

java中的Thread类解析

实现线程的三种方式 1、继承Thread类&#xff0c;重写里面的run方法 public class MyThread extends Thread{Overridepublic void run() {System.out.println("threadName:"Thread.currentThread().getName());}}/*** 方式一&#xff1a;继承Thread类&#xff0c;重…...

如何正确清理DNS缓存

前言 有些场景&#xff0c;需要刷新自己本机的DNS缓存&#xff0c;比如说某个cdn访问不到&#xff0c;某个网络不通等等&#xff0c;都有可能是由于DNS缓存记录了错误的ip映射关系而导致的。本文介绍下如何刷新本机的DNS缓存。 Mac 如果你是mac用户&#xff0c;执行以下操作…...

Git从基础到实践

1.Git是用来做什么的&#xff1f; git就是一款版本控制软件&#xff0c;主要面向代码的管理。你可以理解为Git是一个代码的备份器&#xff0c;给你的每一次修改后的代码做个备份&#xff0c;防止丢失&#xff0c;这个是git最基本的功能。 其次,git不止备份,当你需要比对多…...

C 保留字解释

语句 // 单行注释 /* */ 多行注释 #include 头文件引入声明 #define 预先定义 return 结果返回语句&#xff08;可以带参数&#xff0c;也可不带参数&#xff09; printf(); 输出 if 条件语句 else 条件语句否定分支&#xff08;和 if 连用&a…...

【Web】https 与 http 的区别

文章目录 一、基本概念二、区别对比 一、基本概念 http &#xff1a;超文本传输协议&#xff0c;一种网络传输协议&#xff0c;一个客户端和服务器请求和应答的标准&#xff08;TCP&#xff09;。 https &#xff1a;简单讲就是在http基础上 使用 SSL 或 TLS 对请求和响应进行…...

【KVM】半虚拟化和全虚拟化技术

前言 大家好&#xff0c;我是秋意零。 上一篇的介绍了软件和硬件虚拟化类型&#xff0c;现在来看看半虚拟化技术和通过硬件虚拟化类型辅助的全虚拟化技术吧&#xff01; &#x1f47f; 简介 &#x1f3e0; 个人主页&#xff1a; 秋意零&#x1f525; 账号&#xff1a;全平台…...

react中的useReducer复杂的状态管理

一、useReducer reducer官网教程 useReducer 是 React 提供的一个用于状态管理的 Hook。它可以替代 useState&#xff0c;更适用于处理复杂的状态逻辑。 useReducer 接受一个reducer函数和一个初始状态&#xff0c;并返回当前状态以及一个 dispatch 函数&#xff0c;用来触发…...

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库绘制颜色渐变的高级散点图

前言 我的科研论文中需要绘制一个精美的散点图&#xff0c;表达的是各个散点距离中心点的距离远近情况&#xff0c;特点如下&#xff1a; 绘图的美观程度高根据距离目标点的距离的不同&#xff0c;各个散点能有颜色或者是透明度上的区分相应的统计量是与中心点&#xff08;目…...

根据Word模板,使用POI生成文档

突然想起来有个小作业&#xff1a;需要根据提供的Word模板填充数据。这里使用POI写了一个小demo验证下。 测试用模板&#xff1a; 执行结果 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地球

效果图&#xff1a; 直接放源码 <!DOCTYPE html> <html> <head><meta http-equiv"Content-Type" content"text/html; charsetutf-8" /><meta name"viewport" content"initial-scale1.0, user-scalableno" …...

安全组问题 访问华为云服务器端口

一些常用的安全组的配置示例&#xff0c;包括远程登录云服务器&#xff0c;对外提供网站访问、不同安全组内实例内网互通等。 通常情况下&#xff0c;安全组默认拒绝所有来自外部的请求。您需要遵循白名单原则添加安全组入方向规则&#xff0c;允许来自外部的特定请求访问安全组…...

音视频常见问题(七):首开慢

本文主要讨论音视频应用中的首开慢问题&#xff0c;文章介绍了首开慢的产生原因&#xff1a;DNS解析耗时、网络传输协议耗时、传输网络调度耗时&#xff0c;并提供了排查方式和解决方案。即构科技的Express SDK和MSDN网络可以有效的解决首开慢问题&#xff0c;且节省开发成本。…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...