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网络可以有效的解决首开慢问题,且节省开发成本。…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
