力扣hot100 打家劫舍 DP 滚动数组

news/2024/2/25 12:27:40/文章来源:https://blog.csdn.net/lt6666678/article/details/135626956

Problem: 198. 打家劫舍
在这里插入图片描述

文章目录

  • 思路
  • 复杂度
  • 💖 Code
  • 💖 DP空间优化版

思路

👨‍🏫 参考地址
在这里插入图片描述

复杂度

时间复杂度: O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n)

💖 Code

class Solution {public static int rob(int[] nums){int n = nums.length;if (n == 1)return nums[0];int[] f = new int[n + 1];//f[i] 表示在前 i 间房屋里能偷窃到的 最大 金额
//		初始化f[0] = 0;//偷 0 家金额为 0f[1] = nums[0];
//		状态转移for (int i = 2; i <= n; i++)
//							 偷当前家                      不偷当前家f[i] = Math.max(f[i - 2] + nums[i-1], f[i - 1]);return f[n];}
}

💖 DP空间优化版

空间复杂度: O ( 1 ) O(1) O(1)

public int rob(int[] nums) {int prev = 0;int curr = 0;// 每次循环,计算“偷到当前房子为止的最大金额”for (int i : nums) {// 循环开始时,curr 表示 dp[k-1],prev 表示 dp[k-2]// dp[k] = max{ dp[k-1], dp[k-2] + i }int temp = Math.max(curr, prev + i);prev = curr;curr = temp;// 循环结束时,curr 表示 dp[k],prev 表示 dp[k-1]}return curr;
}

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

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

相关文章

七、Qt 信号和槽

在QT4以上的版本&#xff0c;在窗体上用可以通过选中控件&#xff0c;然后点击鼠标右键单击按钮&#xff0c;选择“转到槽”。可以自动创建信号和槽。 选择clicked(),并点击 ok Qt Creator会给头文件和代码文件自动添加 这个按钮的单击事件&#xff08;信号和槽&#xff09;。 …

【征服redis5】redis的Redisson客户端

目录 1 Redisson介绍 2. 与其他Java Redis客户端的比较 3.基本的配置与连接池 3.1 依赖和SDK 3.2 配置内容解析 4 实战案例&#xff1a;优雅的让Hash的某个Field过期 5 Redisson的强大功能 1 Redisson介绍 Redisson 最初由 GitHub 用户 “mrniko” 创建&#xff0c;并在…

蓝桥杯练习题(九)

&#x1f4d1;前言 本文主要是【算法】——蓝桥杯练习题&#xff08;九&#xff09;的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 …

网络基础学习(3):交换机

1.交换机结构 &#xff08;1&#xff09;网线接口和后面的电路部分加在一起称为一个端口&#xff0c;也就是说交换机的一个端口就相当于计算机上的一块网卡。 如果在计算机上安装多个网卡&#xff0c;并让网卡接收所有网络包&#xff0c;再安装具备交换机功能的软件&#xff0…

介绍下Redis?Redis有哪些数据类型?

一、Redis介绍 Redis全称&#xff08;Remote Dictionary Server&#xff09;本质上是一个Key-Value类型的内存数据库&#xff0c;整个数据库统统加载在内存当中进行操作&#xff0c;定期通过异步操作把数据库数据flush到硬盘上进行保存。因为是纯内存操作&#xff0c;Redis的性…

【零基础入门Python数据分析】Anaconda3 JupyterNotebookseaborn版

目录 一、安装环境 python介绍 anaconda介绍 jupyter notebook介绍 anaconda3 环境安装 解决JuPyter500&#xff1a;Internal Server Error问题-CSDN博客 Jupyter notebook快捷键操作大全 二、Python基础入门 数据类型与变量 数据类型 变量及赋值 布尔类型与逻辑运算…

【HarmonyOS】消息通知场景的实现

从今天开始&#xff0c;博主将开设一门新的专栏用来讲解市面上比较热门的技术 “鸿蒙开发”&#xff0c;对于刚接触这项技术的小伙伴在学习鸿蒙开发之前&#xff0c;有必要先了解一下鸿蒙&#xff0c;从你的角度来讲&#xff0c;你认为什么是鸿蒙呢&#xff1f;它出现的意义又是…

SpringAOP-说说 JDK动态代理和 CGLIB 代理

Spring 的 AOP 是通过动态代理来实现的&#xff0c;动态代理主要有两种方式 JDK 动态代理和 Cglib 动态代理&#xff0c;这两种动态代理的使用和原理有些不同。 JDK 动态代理 Interface&#xff1a;JDK动态代理是基于接口的代理&#xff0c;它要求目标类实现一个接口。Invoca…

通过OpenIddict设计一个授权服务器02-创建asp.net项目

在这一部分中&#xff0c;我们将创建一个ASPNET核心项目&#xff0c;作为我们授权服务器的最低设置。我们将使用MVC来提供页面&#xff0c;并将身份验证添加到项目中&#xff0c;包括一个基本的登录表单。 创建一个空的asp.net core项目 正如前一篇文章中所说&#xff0c;授权…

PSoc62™开发板之i2c通信

实验目的 使用模拟i2c接口读取温湿度气压模块BME280数据 实验准备 PSoc62™开发板温湿度气压模块BME280公母头杜邦线 板载资源 本次实验是通过模拟i2c时序的方式来进行通信&#xff0c;理论上可以有非常多的方式配置i2c引脚&#xff0c;不像硬件i2c那样芯片出厂引脚已经固…

SpringBoot教程(十二) | SpringBoot集成JPA

SpringBoot教程(十二) | SpringBoot集成JPA 1. JPA简介 概念&#xff1a; JPA顾名思义就是Java Persistence API的意思&#xff0c;是JDK 5.0注解或XML描述对象&#xff0d;关系表的映射关系&#xff0c;并将运行期的实体对象持久化到数据库中。 优势&#xff1a; 标准化 …

信息系统安全——Linux 访问控制机制分析

实验 4 Linux 访问控制机制分析 4.1 实验名称 《Linux 访问控制机制分析》 4.2 实验目的 1 、熟悉 Linux基本访问控制机制使用和原理 2 、熟悉 Linux S 位的作用和使用 3 、熟悉强制访问控制 Selinux 原理及其使用 4.3 实验步骤及内容 1 、Linux 基本访问控制机制 &#xff08…

渗透测试(8)- Kali Linux 系统概述

Kali Linux 是一个基于 Debian 的 Linux 发行版&#xff0c;包括很多安全和取证方面的相关工具。Kali Linux 是一款全功能的安全操作系统&#xff0c;它可以帮助用户完成各种安全任务&#xff0c;包括网络渗透测试、系统攻击、密码破解、恶意软件分析、社会工程学攻击等&#x…

buuctf[极客大挑战 2019]BabySQL--联合注入、双写过滤

目录 1、测试万能密码&#xff1a; 2、判断字段个数 3、尝试联合注入 4、尝试双写过滤 5、继续尝试列数 6、查询数据库和版本信息 7、查询表名 8、没有找到和ctf相关的内容&#xff0c;查找其他的数据库 9、查看ctf数据库中的表 10、查询Flag表中的字段名 11、查询表…

新能源汽车智慧充电桩方案:如何实现充电停车智慧化管理?

一、方案概述 基于新能源汽车充电桩的监管运营等需求&#xff0c;安徽旭帆科技携手合作伙伴触角云共同打造“智能充电设备&#xff0b;云平台&#xff0b;APP小程序”一体化完整的解决方案&#xff0c;为充电桩车位场所提供精细化管理车位的解决办法&#xff0c;解决燃油车恶意…

Python+Django+MySQL的图书馆管理系统【附源码,运行简单】

PythonDjangoMySQL的图书馆管理系统【附源码&#xff0c;运行简单】 总览 1、《图书馆管理系统》1.1 方案设计说明书设计目标需求分析工具列表 2、详细设计2.1 登录2.2 注册2.3 程序主页面2.4 图书新增界面2.5 图书信息修改界面2.6 其他功能贴图 3、下载 总览 自己做的项目&am…

测试覆盖率 之 Cobertura的使用

什么是代码覆盖率&#xff1f; 代码覆盖率是对整个测试过程中被执行的代码的衡量&#xff0c;它能测量源代码中的哪些语句在测试中被执行&#xff0c;哪些语句尚未被执行。 为什么要测量代码覆盖率&#xff1f; 众所周知&#xff0c;测试可以提高软件版本的质量和可预测性。…

【力扣·每日一题】2085.统计出现过一次的公共字符串(模拟 哈希表 优化 C++ Go)

题目链接 题意 给你两个字符串数组 words1 和 words2 &#xff0c;请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。 输入&#xff1a;words1 [“leetcode”,“is”,“amazing”,“as”,“is”], words2 [“amazing”,“leetcode”,“is”] 输出&#xff1a;2 …

Java爬虫爬取图片壁纸

Java爬虫 以sougou图片为例&#xff1a;https://pic.sogou.com/ JDK17、SpringBoot3.2.X、hutool5.8.24实现Java爬虫&#xff0c;爬取页面图片 项目介绍 开发工具&#xff1a;IDEA2023.2.5 JDK&#xff1a;Java17 SpringBoot&#xff1a;3.2.x 通过 SpringBoot 快速构建开发环境…

Baumer工业相机堡盟工业相机如何使用OpenCV实现相机图像的显示(C#)

Baumer工业相机堡盟工业相机如何使用OpenCV实现相机图像的显示&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机的图像转换为OpenCV的Mat图像的技术背景在NEOAPI SDK里使用OpenCV实现相机图像的显示联合OpenCV实现相机图像的显示测试演示图 工业相机通过使用OpenCV实现…