leetCode 198.打家劫舍 动态规划

198. 打家劫舍 - 力扣(LeetCode)

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

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

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

>>思路和分析

  • 常见困惑(•_•)? : 当前的状态我是偷呢 还是 不偷呢?
  • 破解困惑:当前房屋偷与不偷取决于前一个房屋和前两个房屋是否被偷了~
  • 当前状态和前面状态具有一种依赖关系,可用动规的递推公式

>>动规五部曲

1.确定dp数组(dp table)以及下标的含义

        dp[i] : 考虑下标i(包括 i)以内的房屋,最多可以偷窃的金额为 dp[i]

2.确定递推公式

决定 dp[i] 的因素就是第 i 个房间  或者 不偷

① 考虑偷的情况

  • 如果偷第 i 个房间,那么 dp[i] = dp[i - 2] + nums[i] ,即: 第 i - 1 个房一定是不考虑的,找出下标 i - 2(包括 i - 2)以内的房屋,最多可以偷窃的金额为 dp[i - 2] 加上第 i 个房间偷到的钱。

 ② 考虑不偷的情况

  • 如果不偷第 i 个房间,那么dp[i] = dp[i - 1],即考虑 i - 1房(注意这里是考虑,并不是一定要偷 i - 1

dp[i] 取这两种情况的最大值, dp[i] = max(dp[i - 2] + nums[i],dp[i - 1]);

3.dp数组初始化

从递推公式 dp[i] = max(dp[i - 2] + nums[i],dp[i - 1]);可以看出,递推公式的基础就是dp[0] 和 dp[1]。

  • dp[0] = nums[0];
  • dp[1] = max(nums[0],nums[1]);
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);

4.确定遍历顺序

dp[i] 是根据 dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历!!!

for (int i = 2; i < nums.size(); i++) {dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}

5.举例推导 dp 数组

输入[2,7,9,3,1] 和 [2,7,9,6,1]

class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];vector<int> dp(nums.size(),0);dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(int i=2;i < nums.size();i++) {dp[i] = max(dp[i-1],dp[i-2] + nums[i]);}return dp[nums.size()-1];}
};// 时间复杂度: O(n)
// 空间复杂度: O(n)
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

>>参考和推荐文章、视频 

代码随想录 (programmercarl.com)

动态规划,偷不偷这个房间呢?| LeetCode:198.打家劫舍_哔哩哔哩_bilibili

打家劫舍是DP解决的经典题目,这道题也是打家劫舍入门级题目,后面我们还会变种方式来打劫的。

来自代码随想录的课堂截图:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/144227.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Hash Index 原理和应用精讲

线上沙龙 - 技术流第 35 期回放来啦 本期直播我们邀请到 KaiwuDB 高级研发工程师徐胜康&#xff0c;为大家分享 Hash Index 原理和应用。徐老师曾任职于 Sun Micro Systems, Lucent 等公司&#xff0c;具备多年 Linux/UNIX Operating System 内核、驱动、文件系统、数据库、研…

java生成PDF的Util

java使用itext生成pdf-CSDN博客 接上文 支持绘制表格 支持表格中的文本 字体加粗、字体上色、单元格背景上色&#xff0c; 支持拼接文本 支持单行文本 多种背景颜色、字体上色 支持自定义水印 废话不说先上效果图 工具类代码 package com.zxw.文件.PDF.util;import com.…

本地搭建kafka并用java实现发送消费消息

1、下载kafka的jar包文件 https://www.apache.org/dyn/closer.cgi?path/kafka/3.1.0/kafka_2.12-3.1.0.tgz2、下载完成直接操作命令启动 1、打开新的terminal(终端)窗口&#xff0c;进入kafka的bin目录 启动zk./zookeeper-server-start.sh ../config/zookeeper.properties2、…

LinkedList与链表

目录 一、Arraylist的缺陷 二、链表 2.1 链表的概念和结构 2.2 链表的实现 三、链表面试题 3.1 删除链表中所有值为val的节点 3.2 反转一个单链表 3.3 链表的中间节点 3.4 将有序链表合并 3.5 输出倒数第k个节点 3.6 链表分割 3.7 链表的回文结构 3.8 找两个链表的公共节…

现场直击|亚数TrustAsia精彩亮相IOTE深圳物联网展,CSA联盟展台等你来!

2023年9月20日&#xff0c;IOTE 2023第二十届深圳国际物联网展在深圳国际会展中心&#xff08;宝安&#xff09;顺利开幕。作为物联网领域年度最重要的行业盛会之一&#xff0c;本次展会汇聚全球来自工业、物流、基建、智慧城市、智慧零售等领域的600企业、10万行业人士&#x…

严重影响Windows使用体验的一些建议

1内存不够用&#xff1a;通过观察我发现我的电脑已经评价到了90%的内存使用率 没有内存什么程序运行起来都会卡的&#xff0c;所以一定要把不用的PROGRAME给他删除掉。特别是那些自动启动的软件&#xff0c;如果实在不行&#xff0c;就把杀毒也给他卸载掉。 不良具体表现&…

Java基础面试题精选:深入探讨哈希表、链表和接口等

目录 1.ArrayList和LinkedList有什么区别&#xff1f;&#x1f512; 2.ArrayList和Vector有什么区别&#xff1f;&#x1f512; 3.抽象类和普通类有什么区别&#xff1f;&#x1f512; 4.抽象类和接口有什么区别&#xff1f;&#x1f512; 5.HashMap和Hashtable有什么区别&…

Ubuntu为什么键盘会出现乱字符

今天上午起来只是要简单打一个命令&#xff0c;需要输入一个"双引号&#xff0c;但是总是显示&#xff0c;我一开始以为是中了病毒&#xff0c;把键盘给改了&#xff0c;后来发现虚惊一场&#xff1a;出现这个原因是因为ubuntu的键盘设置有问题。 我把键盘设置为英国英语…

【C++进阶(六)】STL大法--栈和队列深度剖析优先级队列适配器原理

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; 栈和队列 1. 前言2. 栈和队列的接口函数熟悉3. …

欧伟杰博士:突破算力边界,YashanDB实现理论与工程双重突围

作者介绍 *全文4767个字&#xff0c;阅读时长约12分钟。 背景 随着数字化进程的加速&#xff0c;数据处理的规模和速度需求持续攀升。传统数据库系统在处理大规模数据时&#xff0c;存在单表记录数不超过500万条的限制&#xff0c;这已成为业务发展的瓶颈。为了解决此问题&…

No146.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

MySQL5.7高级函数:JSON_ARRAYAGG和JSON_OBJECT的使用

前置准备 DROP TABLE IF EXISTS t_user; CREATE TABLE t_user (id bigint(20) NOT NULL,name varchar(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_ci …

杀掉进程但是fastapi程序还在运行

两个脚本&#xff0c;一个运行fastapi服务&#xff0c;一个重启服务&#xff1a; 启动服务先&#xff1a; 发现问题&#xff0c;杀掉 server.sh 后&#xff0c;依旧有&#xff1a; 不知道为什么会出现这个&#xff0c;直接kill吧&#xff1a; server.sh: #!/bin/bashparpath/…

led灯什么牌子的质量好?Led护眼台灯排行榜

现在我们很多家长对自己孩子的视力十分关心&#xff0c;生怕自己的孩子是近视、远视、弱视等等。对于父母而言&#xff0c;在孩子读书压力大课业重的关键时期&#xff0c;为孩子选择合适的桌椅&#xff0c;保护灯具从而保护孩子的眼睛是非常重要的事情!那么买给孩子读书做功课的…

Matlab绘图函数subplot、tiledlayout、plot和scatter

一、绘图函数subplot subplot(m,n,p)将当前图窗划分为 mn 网格&#xff0c;并在 p 指定的位置创建坐标区。MATLAB按行号对子图位置进行编号。第一个子图是第一行的第一列&#xff0c;第二个子图是第一行的第二列&#xff0c;依此类推。如果指定的位置已存在坐标区&#xff0c;…

基于Java的音乐网站管理系统设计与实现(源码+lw+部署文档+讲解等)

文章目录 前言具体实现截图详细视频演示为什么选择我自己的网站自己的小程序&#xff08;小蔡coding&#xff09;有保障的售后福利 代码参考源码获取 前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&…

前端uniapp防止页面整体滑动页面顶部以上,设置固定想要固定区域宽高

解决&#xff1a;设置固定想要固定区域宽高 目录 未改前图未改样式改后图改后样式 未改前图 未改样式 .main {display: flex;flex-direction: row;// justify-content: space-between;width: 100vw;// 防止全部移动到上面位置&#xff01;&#xff01;&#xff01;&#xff01…

No147.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…

【在Ubuntu部署Docker项目】— PROJECT#1

一、说明 让我们深入了解 Docker。用docker构建web服务器。我们正在计划开发JavaScript API&#xff0c;建立MySQL数据库&#xff0c;并创建一个 PHP 网站使用 API 服务。Php Node.js Mysql — DockerSeries — Episode#1 二、系统架构概述 我们要构建的容器&#xff0c;是三…

Qt_C++读写NFC标签Ntag支持windows国产linux操作系统

本示例使用的发卡器&#xff1a;Android Linux RFID读写器NFC发卡器WEB可编程NDEF文本/智能海报/-淘宝网 (taobao.com) ntag2标签存储结构说明 #include "mainwindow.h" #include "./ui_mainwindow.h" #include <QDebug> #include "QLibrary&…