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

leetcode 198. House Robber

news 来源：原创 2025/9/6 23:36:00

本题是动态规划问题。

第一步，明确并理解dp数组以及下标的含义

dp[i]表示从第0号房间一直到第i号房间(包含第i号房间)可以偷到的最大金额，具体怎么偷这里不考虑，第i+1号及之后的房间也不考虑。换句话说，dp[i]也就是只考虑[0,i]号房间，无论怎么偷可以偷到的最大金额。

按照这个定义，dp[n-1]就是答案。需要注意的是，dp[i]一定能求到值，不代表一定是偷了第i号房间才求得dp[i]。

第二步，明确并理解递推公式

考虑第i号房间，只有两种可能，偷或者不偷。

偷第i号房间，则第i-1号房间肯定不能偷，此时能获得的总金额为dp[i] = dp[i-2] + nums[i]。

不偷第i号房间，此时dp[i]应该等于dp[i-1]。

第三步，理解dp数组如何初始化

dp[0]应该初始化为第0号房间的金额。因为只有一间房的时候，能偷到的最大金额显然就是把它偷了。

dp[1]，含义是从第0号房间和第1号房间偷，能偷到的最大金额。由于相邻的房间不能都偷，所以dp[1]= max(nums[0],numd[1]);

i>=2的dp[i]可以不初始化，或者说无论初始化为多大都没关系，因为dp[i]只和dp[i-1],dp[i-2],nums[i]有关系。

第四步，理解遍历顺序

因为dp[i]依赖于它前面的dp[i-1]和dp[i-2]，所以i的遍历顺序肯定要从小到大。

代码

按照上面的思路，先初始化dp[0]和dp[1]，再让i从2开始遍历，含义更加明确，代码更好理解，如下所示：

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();//dp[i]表示从第0号房间一直到第i号房间(包含第i号房间)可以偷到的最大金额。//按照这个定义，dp[n-1]就是答案vector<int> dp(n);dp[0] = nums[0];if(n < 2)return dp[0];dp[1] = max(nums[0],nums[1]);for(int i = 2;i < n;i++){//偷第i号房间int temp1 = dp[i-2] + nums[i];//不偷第i号房间int temp2 = dp[i-1];dp[i] = max(temp1,temp2);}return dp[n-1];}
};

但实际上，也可以不初始化让i从0开始遍历，代码如下所示：

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();//dp[i]表示从第0号房间一直到第i号房间(包含第i号房间)可以偷到的最大金额。//按照这个定义，dp[n-1]就是答案vector<int> dp(n);for(int i = 0;i < n;i++){//偷第i号房间int temp1 = (i >= 2 ? dp[i-2]:0) + nums[i];//不偷第i号房间int temp2 = i >= 1 ? dp[i-1]:0;dp[i] = max(temp1,temp2);}return dp[n-1];}
};

相关文章：

leetcode 198. House Robber

本题是动态规划问题。 第一步&#xff0c;明确并理解dp数组以及下标的含义 dp[i]表示从第0号房间一直到第i号房间(包含第i号房间)可以偷到的最大金额&#xff0c;具体怎么偷这里不考虑&#xff0c;第i1号及之后的房间也不考虑。换句话说&#xff0c;dp[i]也就是只考虑[0,i]号…...

编程日记 2025/9/6 23:36:00

【2025软考高级架构师】——软件架构设计（4）

摘要 本文主要介绍了几种软件架构设计相关的概念和方法。包括C2架构风格的规则&#xff0c;模型驱动架构&#xff08;MDA&#xff09;的起源、目标、核心模型及各模型之间的关系&#xff1b;软件架构复用的概念、历史发展、维度、类型及相关过程&#xff1b;特定领域架构&…...

编程日记 2025/9/4 14:29:10

分发饼干问题——用贪心算法解决

目录 一&#xff1a;问题描述 二&#xff1a;解决思路 贪心策略&#xff08;C语言&#xff09;算法复习总结3——贪心算法-CSDN博客 三&#xff1a;代码实现 四&#xff1a;复杂度分析 一&#xff1a;问题描述 分发饼干问题是一个经典的可以使用贪心算法解决的问题&#xf…...

编程日记 2025/9/1 10:01:04

深入详解MYSQL的MVCC机制

参考资料： 参考视频（注意第二个视频关于幻读的讲解是错误的，详情见本文） redoLog的结构详解 参考资料 学习内容： 1. MVCC要解决的问题 MVCC要解决的问题是，在不产生脏读等数据库问题的前提下，数据库的查询语句和更改语句不相互阻塞的情况； 在InnoDB中，MVCC仅仅存…...

编程日记 2025/9/6 8:01:48

DNS域名解析

目录 一.DNS 1.1DNS的简介 1.2DNS的背景 1.3DNS的架构 1.4实现DNS的方式 1.5DNS的查询类型 1.6DNS解析的基本流程 二.主从复制 2.1定义 2.2优缺点 三.DNS服务软件 3.1bind 3.1.1定义 3.1.2bind相关文件 3.2DNS服务器的核心文件 3.2.1主配置文件 3.2.2域名文件 …...

编程日记 2025/9/6 7:30:41

Java基础：一文讲清多线程和线程池和线程同步

01-概述 02-线程创建 继承Thread 实现Runnable(任务对象) 实现Callable接口 public class ThreadDemo3 {public static void main(String[] args) throws ExecutionException, InterruptedException {// 目标&#xff1a;线程创建3// 需求&#xff1a;求1-100的和Callable<…...

编程日记 2025/9/4 0:12:05

ubuntu 20.04 连不上蓝牙耳机/蓝牙鼠标

sudo gedit /etc/bluetooth/main.conf改为 ControllerMode dual然后重启蓝牙服务 sudo service bluetooth restart...

编程日记 2025/8/17 21:05:26

SaaS、Paas、IaaS、MaaS、BaaS五大云计算服务模式

科普版&#xff1a;通俗理解五大云计算服务模式 1. SaaS&#xff08;软件即服务&#xff09; 一句话解释&#xff1a;像“租用公寓”&#xff0c;直接使用现成的软件&#xff0c;无需操心维护。 案例&#xff1a;使用钉钉办公、在网页版WPS编辑文档。服务提供商负责软件更新和…...

编程日记 2025/9/5 3:09:23

【深拷贝、浅拷贝】golang函数参数传递，变量复制后，操作变量参数，是否影响原有数据？全面解析

Golang中深拷贝与浅拷贝的详细解析&#xff0c;以及变量复制、函数参数传递等场景下对新旧变量影响的总结&#xff1a; 一拷贝与浅拷贝的核心区别 1. 浅拷贝&#xff08;Shallow Copy&#xff09; • 定义&#xff1a;仅复制数据的顶层结构&#xff0c;对引用类型字段&#x…...

编程日记 2025/9/2 17:15:41

c语言编程经典习题详解3

21. 求给定正整数 n 以内的素数之积 定义：找出小于给定正整数n的所有素数，并将它们相乘。要点：使用双层for循环，外层循环遍历小于n的数，内层循环判断是否为素数，若是则累乘。应用：在数论研究、密码学等领域有应用。c #include <stdio.h>int isPrime(int num) {if…...

编程日记 2025/8/31 10:59:08

【HD-RK3576-PI】Docker搭建与使用

硬件&#xff1a;HD-RK3576-PI 软件&#xff1a;Linux6.1Ubuntu22.04 1. 安装Docker Docker安装脚本下载&#xff1a; roothd-rk3576-pi:~ $ curl -fsSL https://test.docker.com -o test-docker.sh 可以直接执行安装 roothd-rk3576-pi:~ $ sh test-docker.sh 2. 配置国内镜…...

编程日记 2025/9/5 5:24:44

C++进阶——异常

目录 1、异常的概念及使用 1.1 异常的概念 1.2 异常的抛出和捕获 1.3 栈展开 1.4 查找匹配的处理代码 1.5 异常的重新抛出 1.6 异常的安全问题 1.7 异常的规范 2、标准库的异常(了解) 1、异常的概念及使用 1.1 异常的概念 C语言&#xff0c;出错了&#xff0c;就报错…...

编程日记 2025/8/20 7:38:06

Linux安装开源版MQTT Broker——EMQX服务器环境从零到一的详细搭建教程

零、EMQX各个版本的区别 EMQX各个版本的功能对比详情https://docs.emqx.com/zh/emqx/latest/getting-started/feature-comparison.html...

编程日记 2025/8/17 19:08:34

C++ 编程指南36 - 使用Pimpl模式实现稳定的ABI接口

一&#xff1a;概述 C 的类布局&#xff08;尤其是私有成员变量&#xff09;直接影响它的 ABI&#xff08;应用二进制接口&#xff09;。如果你在类中添加或修改了私有成员&#xff0c;即使接口不变&#xff0c;编译器生成的二进制布局也会变&#xff0c;从而导致 ABI 不兼容。…...

编程日记 2025/8/29 17:49:01

笔记本电脑突然无法开机电源灯亮但是屏幕无法点亮

现象 按电源键&#xff0c;电源灯点亮&#xff0c;屏幕没动静 风扇开始运转&#xff0c;然后一会儿就不转了&#xff1b;屏幕一直没动静&#xff0c;屏幕没有任何反应&#xff08;没有系统启动画面&#xff0c;没有徽标显示&#xff0c;就一点反应也没用&#xff09; 这个问…...

编程日记 2025/9/5 7:08:19

mongodb 4.0+多文档事务的实现原理

1. 副本集事务实现&#xff08;4.0&#xff09;‌ ‌非严格依赖二阶段提交‌ MongoDB 4.0 在副本集环境中通过 ‌全局逻辑时钟&#xff08;Logical Clock&#xff09;‌ 和 ‌快照隔离&#xff08;Snapshot Isolation&#xff09;‌ 实现多文档事务&#xff0c;事务提交时通过…...

编程日记 2025/9/5 14:48:19

decompiled.class file bytecode version50(java 6)

idea运行项目报错&#xff0c;跳到具体的.class中&#xff0c;idea会给出提示下载源码&#xff0c;点击下载报错&#xff0c;具体报错信息我没记录了&#xff08;反正就是无法看到源码&#xff09; 解决方式&#xff1a; 1、网上说下载scala插件&#xff0c;重启idea即可 但是…...

编程日记 2025/9/1 13:44:33

CSS 列表样式学习笔记

CSS 列表样式提供了强大的功能&#xff0c;用于定制 HTML 列表的外观。通过 CSS&#xff0c;可以轻松地改变列表项的标记类型、位置&#xff0c;甚至使用图像作为列表项标记。以下是对 CSS 列表样式的详细学习笔记。 一、HTML 列表类型 在 HTML 中&#xff0c;主要有两种类型…...

编程日记 2025/9/3 0:42:24

linux网络设置

ifconfig 查看ip地址 查看当前的liunx系统的网络参数ip地址 Ubuntu需要安装 Apt install -y net-tools 查看网络信息 Ifconfig 只能看到开启的网卡 Ifconfig -a 看到所有的网卡包括开启和关闭的 Ifconfig 网卡名称 up 开启网卡 Ifconfig 网卡名称 down 关闭网卡 If…...

编程日记 2025/8/27 4:50:54

抗干扰CAN总线通信技术在分布式电力系统中的应用

摘要&#xff1a;随着分布式电力系统的广泛应用&#xff0c;其通信系统的可靠性与稳定性受到了前所未有的挑战。CAN总线通信技术以其卓越的抗干扰性能和可靠性&#xff0c;在众多通信技术中脱颖而出&#xff0c;成为解决分布式电力系统通信问题的关键。本文深入剖析了CAN总线通…...

编程日记 2025/9/1 21:57:45

Maven工具学习使用（十二）——extension和depency的区别

在 Maven 中&#xff0c;extensions 和 dependencies 是两个不同的概念&#xff0c;它们在项目构建和依赖管理中扮演着不同的角色。 1、Dependencies dependencies 是 Maven 项目中用于管理项目所需的库和模块的部分。这些依赖可以是本地仓库中的&#xff0c;也可以是远程仓库…...

编程日记 2025/9/4 11:55:10

Python学生信息查询

利用字典设置学生信息&#xff0c;将这些信息放入列表中进行存储&#xff0c;根据输入的姓名查询展示对应的学生信息。 Student1{no:202001,name:zyt,score:87} Student2Student1.copy() Student3Student2.copy()Student2[no]202002 Student3[no]202003Student2[name]zwh Stud…...

编程日记 2025/9/5 11:22:21

一天时间，我用AI(deepseek)做了一个配色网站

前言 最近在开发颜色搭配主题的相关H5和小程序&#xff0c;想到需要补充一个web网站&#xff0c;因此有了这篇文章。 一、确定需求 向AI要答案之前&#xff0c;一定要清楚自己想要做什么。如果你没有100%了解自己的需求&#xff0c;可以先让AI帮你理清逻辑和思路&#xff0c;…...

编程日记 2025/8/31 15:38:52

MQ（消息队列）体系详解

消息队列&#xff08;MQ&#xff0c;Message Queue&#xff09; 是一种基于消息传递的异步通信机制&#xff0c;用于不同系统、服务之间进行数据传递和交互。它通常用来解耦生产者和消费者&#xff0c;提供高可用、高吞吐量和可靠的消息传递。 一、消息队列用途 1.系统解耦 …...

编程日记 2025/9/5 1:47:33

【GESP真题解析】第 3 集 GESP一级样题卷编程题 2：闰年求和

大家好&#xff0c;我是莫小特。 这篇文章给大家分享 GESP 一级样题卷编程题第 2 题&#xff1a;闰年求和。 题目链接 洛谷链接&#xff1a;B3846 闰年求和 一、完成输入 根据题目要求&#xff0c;我们需要输入两个整数&#xff0c;分别表示起始年份和终止年份。 要求计算…...

编程日记 2025/9/6 18:52:41

Windows Server 2019 安装 Docker 完整指南

博主本人使用的是离线安装 1. 安装前准备 系统要求 操作系统&#xff1a;Windows Server 2019&#xff08;或 2016/2022&#xff09;权限&#xff1a;管理员权限的 PowerShell网络&#xff1a;可访问互联网&#xff08;或离线安装包&#xff09; 启用容器功能 Install-Win…...

编程日记 2025/9/5 18:12:29

JetBrains PhpStorm v2024.3.1 Mac PHP开发工具

JetBrains PhpStorm v2024.3.1 Mac PHP开发工具 一、介绍 JetBrains PhpStorm 2024 mac&#xff0c;是一款PHP开发工具&#xff0c;直接开始编码&#xff0c;无需安装和配置大量插件。PhpStorm 从一开始就已包含 PHP、JavaScript 和 TypeScript 开发所需的一切&#xff0c;还…...

编程日记 2025/9/6 2:59:24

机器学习（ML）在AI驱动测试通过数据驱动的智能决策显著提升测试效率、覆盖率和准确性。

机器学习（ML）在AI驱动测试中扮演着 核心引擎 的角色，通过数据驱动的智能决策显著提升测试效率、覆盖率和准确性。以下是机器学习在测试各环节的具体作用及实现方案： 一、机器学习在测试生命周期中的作用 #mermaid-svg-u4vgPE6O2jugiZFB {font-family:"trebuchet ms&qu…...

编程日记 2025/8/17 20:15:31

0x06.Redis 中常见的数据类型有哪些？

回答重点 Redis 常见的数据结构主要有五种，这五种类型分别为：String(字符串)、List(列表)、Hash、Set(集合)、Zset(有序集合，也叫sorted set)。 String 字符串是Redis中最基本的数据类型，可以存储任何类型的数据，包括文本、数字和二进制数据。它的最大长度为512MB。 使…...

编程日记 2025/9/5 5:56:49

本地缓存方案Guava Cache

Guava Cache 是 Google 的 Guava 库提供的一个高效内存缓存解决方案&#xff0c;适用于需要快速访问且不频繁变更的数据。 // 普通缓存 Cache<Key, Value> cache CacheBuilder.newBuilder().maximumSize(1000) // 最大条目数.expireAfterWrite(10, TimeUnit.MINUTES) /…...

编程日记 2025/9/4 20:32:09

A Causal Inference Look at Unsupervised Video Anomaly Detection

标题&#xff1a;无监督视频异常检测的因果推断视角 原文链接&#xff1a;https://ojs.aaai.org/index.php/AAAI/article/view/20053 发表&#xff1a;AAAI-2022 文章目录 摘要引言相关工作无监督视频异常检测因果推断 方法问题公式化一般设置强基线模型 无监督视频异常检测的因…...

编程日记 2025/8/17 20:57:34

MQ(RabbitMQ.1)

MQ的含义及面试题 MQMQ的含义MQ之间的调用的方式MQ的作用MQ的几种产品RabbitMQRabbitMQ的安装RabbitMQ的使用RabbitMQ⼯作流程 AMQPWeb界面操作用户相关操作虚拟主机相关操作 RabbitMQ的代码应用编写生产者代码编写消费者代码 生产者代码消费者代码 MQ MQ的含义 MQ&#xff0…...

编程日记 2025/9/3 8:22:21

cursor+高德MCP：制作一份旅游攻略

高德开放平台 | 高德地图API (amap.com) 1.注册成为开发者 2.进入控制台选择应用管理----->我的应用 3.新建应用 4.点击添加Key 5.在高德开发平台找到MCP的文档 6.按照快速接入的步骤&#xff0c;进行操作 一定要按照最新版的cursor, 如果之前已经安装旧的版本卸载掉重新安…...

编程日记 2025/8/29 18:03:19

FPGA时序分析与约束（11）——时钟组

目录 一、同步时钟与异步时钟 二、逻辑与物理独立时钟 2.1 逻辑独立时钟 2.2 物理独立时钟 三、如何设置时钟组 四、注意事项 专栏目录&#xff1a; FPGA时序分析与约束&#xff08;0&#xff09;——目录与传送门https://ztzhang.blog.csdn.net/article/details/134893…...

编程日记 2025/8/31 12:03:30

opencv 识别运动物体

import cv2 import numpy as npcap cv2.VideoCapture(video.mp4) try:import cv2backSub cv2.createBackgroundSubtractorMOG2() except AttributeError:backSub cv2.bgsegm.createBackgroundSubtractorMOG()#形态学kernel kernel cv2.getStructuringElement(cv2.MORPH_REC…...

编程日记 2025/9/5 15:59:52

opencv实际应用--银行卡号识别

OpenCV&#xff08;Open Source Computer Vision Library&#xff09;是一个开源的计算机视觉库&#xff0c;主要用于图像和视频处理、目标检测、特征提取、3D重建以及机器学习任务。它支持多种编程语言&#xff08;如C、Python&#xff09;&#xff0c;提供丰富的算法和工具&a…...

编程日记 2025/9/4 18:28:12

【软考系统架构设计师】系统架构设计知识点

1、 从需求分析到软件设计之间的过渡过程称为软件架构。 软件架构为软件系统提供了一个结构、行为和属性的高级抽象&#xff0c;由构件的描述、构件的相互作用&#xff08;连接件&#xff09;、指导构件集成的模式以及这些模式的约束组成。 软件架构不仅指定了系统的组织结构和…...

编程日记 2025/9/4 3:49:03

GPT - 2 文本生成任务全流程

数据集下载 数据预处理 import json import pandas as pdall_data []with open("part-00018.jsonl",encoding"utf-8") as f:for line in f.readlines():data json.loads(line)all_data.append(data["text"])batch_size 10000for i in ran…...

编程日记 2025/9/5 10:52:35

重返JAVA之路——面向对象

目录 面向对象 1.什么是面向对象&#xff1f; 2.面向对象的特点有哪些&#xff1f; 3.什么是对象&#xff1f; 4.什么是类&#xff1f; 5.什么是构造方法? 6.构造方法的特性有哪些&#xff1f; 封装 1.什么是封装&#xff1f; 2.封装有哪些特点&#xff1f; 数据隐…...

编程日记 2025/9/3 17:39:38

docker 安装 jenkins

拉取镜像 docker pull jenkins/jenkins:2.426.3-lts-jdk17 创建数据卷 # 创建时即设置安全权限&#xff08;SGID确保组权限继承&#xff09; sudo mkdir -p /var/jenkins_home sudo chmod -R 777 /var/jenkins_home 拉取镜像并运行容器 # 生产环境推荐&#xff08;JDK17…...

编程日记 2025/9/3 13:03:34

sql 向Java的映射

优化建议&#xff0c;可以在SQL中控制它的类型 在 MyBatis 中&#xff0c;如果返回值类型设置为 java.util.Map&#xff0c;默认情况下可以返回 多行多列的数据...

编程日记 2025/9/2 13:54:54

探索Streamlit在测试领域的高效应用：文档读取与大模型用例生成的完美前奏

大模型用例生成前置工作之文档读取——构建你的自动化测试基础 在群友的极力推荐下&#xff0c;开始了streamlit的学习之旅。本文将介绍如何使用Streamlit开发一个多功能文档处理工具&#xff0c;支持读取、预览、格式转换和导出多种测试相关文档&#xff08;YAML、JSON、DOCX…...

编程日记 2025/9/6 11:27:09

Python中数值计算、表格处理和可视化的应用

1.数值计算&#xff1a;Numpy import numpy as np 1.1创建数组 import numpy as np arr1 np.array([[1,2,3,4,5]]) print(arr1) print(type(arr1)) print("数组形状",arr1.shape) arr2 np.array([[1,2,3],[2,3,4]]) print(arr2) print(type(arr1)) print("…...

编程日记 2025/8/31 16:35:23

【数据可视化艺术·实战篇】视频AI+人流可视化：如何让数据“动”起来？

景区游玩&#xff0c;密密麻麻全是人&#xff0c;想找个拍照的好位置都难&#xff1b;上下班高峰挤地铁&#xff0c;被汹涌的人潮裹挟着&#xff0c;只能被动 “随波逐流”。这样的场景&#xff0c;相信很多人都再熟悉不过。其实&#xff0c;这些看似杂乱无章的人群流动现象&am…...

编程日记 2025/9/3 3:55:04

038-flatbuffers

flatbuffers FlatBuffers技术调研报告 一、核心原理与优势 FlatBuffers通过内存直接访问技术实现零拷贝序列化&#xff0c;其核心优势如下&#xff1a; 内存布局&#xff1a;数据以连续二进制块存储&#xff0c;包含VTable&#xff08;虚拟表&#xff09;和Data Object&…...

编程日记 2025/9/4 13:19:44

探索 Go 与 Python：性能、适用场景与开发效率对比

1 性能对比&#xff1a;执行速度与资源占用 1.1 Go 的性能优势 Go 语言被设计为具有高效的执行速度和低资源占用。它编译后生成的是机器码&#xff0c;能够直接在硬件上运行&#xff0c;避免了 Python 解释执行的开销。 以下是一个用 Go 实现的简单循环计算代码&#xff1a; …...

编程日记 2025/9/5 18:36:19

Pinia最基本用法

1. 定义 Store 首先&#xff0c;定义一个 Pinia Store&#xff0c;使用组合式 API 风格和 ref 来管理状态。 示例&#xff1a;stores/ids.js import { defineStore } from pinia; import { ref } from vue;export const useIdsStore defineStore(ids, () > {const ids …...

编程日记 2025/9/5 7:39:20

MySQL中的UNION和UNION ALL【简单易懂】

一、前言 UNION 和 UNION ALL 是 SQL 中用于合并多个查询结果集的关键字。 二、核心作用 两者均用于将多个 SELECT 语句的结果集纵向合并&#xff08;列结构需相同&#xff09;&#xff0c;但行为存在关键差异&#xff1a; 三、使用场景对比 需要去重时&#xff1a;例如合并…...

编程日记 2025/9/3 20:34:00

ConcurrentHashMap 源码分析

摘要 介绍线程安全集合类 ConcurrentHashMap 源码&#xff0c;包括扩容&#xff0c;协助扩容&#xff0c;红黑树节点读写线程同步&#xff0c;插入元素后累加键值对数量操作原子性实现。 1 成员变量及其对应的数据结构 底层由数组红黑树链表实现volatile long baseCount 和 v…...

编程日记 2025/9/6 23:01:29

一种基于学习的多尺度方法及其在非弹性碰撞问题中的应用

A learning-based multiscale method and its application to inelastic impact problems 摘要&#xff1a; 我们在工程应用中观察和利用的材料宏观特性&#xff0c;源于电子、原子、缺陷、域等多尺度物理机制间复杂的相互作用。多尺度建模旨在通过利用固有的层次化结构来理解…...

编程日记 2025/9/4 0:23:19