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

力扣-213打家劫舍II(dp)

力扣-213打家劫舍II

1、题目

213. 打家劫舍 II

你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额

示例 1:

输入:nums = [2,3,2]
输出:3
解释:你不能先偷窃 1 号房屋(金额 = 2),然后偷窃 3 号房屋(金额 = 2), 因为他们是相邻的。

2、分析

  1. 题目。这题与198打家劫舍唯一不同的就是首尾是相连的所以遍历的时候要首不要尾,或者要尾不要首,就这两种情况。
  2. 看到这个题目首先想到的是不能相邻,那么如果要偷其中i的一家,那么我们就需要考虑前面一家i-1就不能偷,i-2的一家就能够偷了,所以,我们大概能够知道这是一道动态规划问题。
  3. 根据上面的分析,dp[i]就是我们偷当前i家的时候,最大金额数。那么我们可得地推公式为:dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i])。
    初始化。
  4. 遍历,两种情况,多个函数进行区间调用

3、代码及注释

class Solution {public int rob(int[] nums) {// 1.第一种就是要最后一个房屋// 2.第二种就是不要最后一个房屋if (nums.length == 0) return 0;if (nums.length == 1) return nums[0];if (nums.length == 2) return Math.max(nums[0], nums[1]);return Math.max(robRange(nums, 0, nums.length - 1), robRange(nums, 1, nums.length));}public int robRange(int[] nums, int start, int end){int[] dp = new int[end];dp[start] = nums[start];dp[start + 1] = Math.max(nums[start + 1], dp[start]);for (int i = start + 2; i < end; i++){dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);}return dp[end - 1];}
}

4、练习

力扣题目链接:213. 打家劫舍 II

相关文章:

力扣-213打家劫舍II(dp)

力扣-213打家劫舍II 1、题目 213. 打家劫舍 II 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#xff0c;相邻的房屋装有相互连通…...

关于【网格结构】岛屿类问题的通用解法DFS(深度遍历)遍历框架+回溯+剪枝总结

最近在刷力扣时遇见的问题&#xff0c;自己总结加上看了力扣大佬的知识总结写下本篇文章&#xff0c;我们所熟悉的 DFS&#xff08;深度优先搜索&#xff09;问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题&#xff0c;是在一种「网格」结构中进行的。岛屿问题…...

【LeetCode】982. 按位与为零的三元组

982. 按位与为零的三元组 题目描述 给你一个整数数组 nums &#xff0c;返回其中 按位与三元组 的数目。 按位与三元组 是由下标 (i, j, k) 组成的三元组&#xff0c;并满足下述全部条件&#xff1a; 0 < i < nums.length0 < j < nums.length0 < k < num…...

Linux内核源码进程原理分析

Linux内核源码进程原理分析一、Linux 内核架构图二、进程基础知识三、Linux 进程四要素四、task_struct 数据结构主要成员五、创建新进程分析六、剖析进程状态迁移七、写时复制技术一、Linux 内核架构图 二、进程基础知识 Linux 内核把进程称为任务(task)&#xff0c;进程的虚…...

电子技术——CMOS反相器

电子技术——CMOS反相器 在本节&#xff0c;我们深入学习CMOS反相器。 电路原理 下图是我们要研究的CMOS反相器的原理图&#xff1a; 下图展示了当输入 vIVDDv_I V_{DD}vI​VDD​ 时的 iD−vDSi_D-v_{DS}iD​−vDS​ 曲线&#xff1a; 我们把 QNQ_NQN​ 当做是驱动源&#x…...

gazebo仿真轨迹规划+跟踪(不在move_base框架下)

以Tianbot为例子&#xff0c;开源代码如下&#xff1a; https://github.com/tianbot/tianbot_mini GitHub - tianbot/abc_swarm: Ant Bee Cooperative Swarm, indicating air-ground cooperation. This repository is for Tianbot Mini and RoboMaster TT swarm kit. 1.在…...

C. Good Subarrays(前缀和)

C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析 这道题目的意思就是给我们一个数组&#xff0c;然后我们从数组中选取一个连续的区间&#xff0c;这个区间满足条件&#xff1a;区间内的元素和等于区间的长度。 对于区间和问题我们先想到的是前缀和的算法。 那…...

关于Facebook Messenger CRM,这里有你想要知道的一切

关于Facebook Messenger CRM&#xff0c;这里有你想要知道的一切&#xff01;想把Facebook Messenger与你的CRM整合起来吗&#xff1f;这篇博文是为你准备的! 我们将介绍有关获得Facebook Messenger CRM整合的一切信息。然后&#xff0c;我们将解释为什么你需要像SaleSmartly&a…...

ChIP-seq 分析:数据与Peak 基因注释(10)

动动发财的小手&#xff0c;点个赞吧&#xff01; 1. 数据 今天&#xff0c;我们将继续回顾我们在上一次中研究的 Myc ChIPseq。这包括用于 MEL 和 Ch12 细胞系的 Myc ChIPseq。 可在此处[1]找到 MEL 细胞系中 Myc ChIPseq 的信息和文件可在此处[2]找到 Ch12 细胞系中 Myc ChIP…...

《C++ Primer Plus》第18章:探讨 C++ 新标准(8)

使用大括号括起的初始化列表语法重写下述代码。重写后的代码不应使用数组 ar&#xff1a; class Z200 { private:int j;char ch;double z; public:Z200(int jv, char chv, zv) : j(jv), ch(chv), z(zv) {} ... };double x 8.8; std::string s "What a bracing effect!&q…...

YOLO-V5 系列算法和代码解析(八)—— 模型移植

文章目录工程目标芯片参数查阅官方文档基本流程Python 版工具链安装RKNPU2的编译以及使用方法移植自己训练的模型工程目标 将自己训练的目标检测模型【YOLO-V5s】移植到瑞芯微【3566】芯片平台&#xff0c;使用NPU推理&#xff0c;最终得到正确的结果。整个过程涉及模型量化、…...

js实现复制拷贝的兼容方法

1. 定义复制拷贝的方法 在某个工具类方法中定义该方法&#xff0c;兼容不同浏览器处理 /*** description 拷贝的类方法*/ class CopyClass {// constructor() {}setRange(input) {return new Promise((resolve, reject) > {try {// 创建range对象const range document.c…...

学习 Python 之 Pygame 开发魂斗罗(八)

学习 Python 之 Pygame 开发魂斗罗&#xff08;八&#xff09;继续编写魂斗罗1. 创建敌人类2. 增加敌人移动和显示函数3. 敌人开火4. 修改主函数5. 产生敌人6. 使敌人移动继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;七&#xff09;中&#xff0…...

Lesson11---分类问题

11.1 逻辑回归 11.1.1 广义线性回归 课程回顾 线性回归&#xff1a;将自变量和因变量之间的关系&#xff0c;用线性模型来表示&#xff1b;根据已知的样本数据&#xff0c;对未来的、或者未知的数据进行估计 11.1.2 逻辑回归 11.1.2.1 分类问题 分类问题&#xff1a;垃圾…...

Python基础学习12——异常

在Python中&#xff0c;会使用“异常”这个十分特殊的对象来管理程序执行期间发生的错误&#xff0c;即报错。本文将介绍一下python基础的处理异常的方法以及一些基本的异常类型。 异常处理方法 try-except代码块 当我们编写程序时&#xff0c;我们可以编写一个try-except代…...

[日常练习]练习17:链表头插法、尾插法练习

[日常练习]练习17&#xff1a;链表头插法、尾插法练习练习17描述输入输出输入示例1输出示例1输入示例2输出示例2代码演示&#xff1a;总结练习17 【日常练习】 链表头插法、尾插法练习 描述 输入3 4 5 6 7 9999一串整数&#xff0c;9999代表结束&#xff0c;通过头插法新建链…...

第十四届蓝桥杯模拟赛(第三期)试题与题解 C++

目录 一、填空题 &#xff08;一&#xff09;最小的十六进制(答案&#xff1a;2730) &#xff08;二&#xff09;Excel的列(答案&#xff1a;BYT) &#xff08;三&#xff09;相等日期(答案&#xff1a;70910) &#xff08;四&#xff09;多少种取法(答案&#xff1a;189)…...

关于 “宏“

起源 宏 Macro"这个词源于希腊语 “makros”&#xff0c;意为“大的&#xff0c;长的” 延伸使用 随后用于计算机领域是&#xff0c;在汇编语言时用于描述一大堆的汇编指令。 只要用宏指令&#xff0c;就是直接用的一大堆的汇编指令&#xff08;有点函数的味道&#xf…...

1.2 CSS标签选择器,类选择器

CSS选择器&#xff1a; 根据不同的需求选出不同的标签&#xff0c;进行美化装饰 1. 标签选择器 标签选择器(元素选择器)&#xff1a;用 HTML标签名作为选择器&#xff0c;按标签名称进行分类&#xff0c;为页面某一类标签指定统一的CSS样式 作用: 可以把某一类标签全部选中&…...

【Linux】进程等待 | 详解 wait/waitpid 的 status 参数

&#x1f923; 爆笑教程 &#x1f449; 《看表情包学Linux》&#x1f448; 猛戳订阅 &#x1f525; &#x1f4ad; 写在前面&#xff1a;在上一章中我们讲解了进程创建与进程终止&#xff0c;本章我们开始讲解进程等待。进程等待这部分知识相较于前面还是较为复杂的&#xff0…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...