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

【leetcode】198. 打家劫舍

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

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

示例 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 <= nums.length <= 100
  • 0 <= nums[i] <= 400

思路 

因为金额要最高,所以小偷开始的位置就限制住了,只能在第1个或者第2个位置就开始。因为如果从第三个及其以后开始,都会漏掉第一个或第二个位置,总金额不可能是最高的。

因为不能是相邻的,但是又得保证最多。所以只能是当前位置前面两个或者前面三个再加上当前位置的值,因此状态转移方程就是 dp[i] = max(dp[i - 3] + nums[i], dp[i - 2] + nums[i]);

返回最大值时,因为不能相邻,所以最大值可能存在的位置有两种可能,倒数第一个位置以及倒数第二个位置,进行比较之后再返回。

代码实现

class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();if(n <= 1){return nums[0];}if(n <= 2){return max(nums[0], nums[1]);}int dp[n];dp[0] = nums[0];dp[1] = nums[1];dp[2] = nums[0] +nums[2];for(int i = 3; i < n; i++){dp[i] = max(dp[i - 3] + nums[i], dp[i - 2] + nums[i]);}return max(dp[n - 2], dp[n - 1]);}
};

贴一下2022年9月份做这一题的思路,当时有点死板

class Solution {
public:int rob(vector<int>& nums) {if(nums.size()==0){return 0;}if(nums.size()==1){return nums[0];}int dp[nums.size()];dp[0]=nums[0];dp[1]=nums[1];for(int i=2;i<nums.size();i++){int max=0;for(int j=0;j<i-1;j++){if(dp[j]>max){max=dp[j];} }dp[i]=max+nums[i];}if(dp[nums.size()-2]>dp[nums.size()-1]){return dp[nums.size()-2];}else{return dp[nums.size()-1];}}
};

相关文章:

【leetcode】198. 打家劫舍

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

【react全家桶学习】react的 (新/旧) 生命周期(重点)

目录 生命周期&#xff08;旧&#xff09; 挂载时的生命周期 constructor&#xff08;props&#xff09; componentWillMount&#xff08;&#xff09;-------------新生命周期已替换 render&#xff08;&#xff09; componentDidMount&#xff08;&#xff09;--- 组件…...

Gradio私网和公网的使用

Gradio私网问题 如果部署的服务器只有私有地址&#xff0c;那么无法直接从外部网络中的其他计算机访问该服务器和其中运行的 Gradio 应用程序。在这种情况下&#xff0c;你可以考虑使用端口转发技术&#xff0c;将服务器的私有地址映射到一定的公开地址上&#xff0c;从而可以…...

ant design vue 配置菜单外部打开

实现如下 菜单配置 前端项目地址&#xff1a;http://localhost:3000 菜单路径&#xff1a;dataCenter/HealthData 打开方式&#xff1a;外部 在项目中src-->config-->router.config.js文件 将需要再外部打开的菜单地址进行如下配置 菜单地址&#xff1a;/dataCenter/Hea…...

YOLOv5/v7 添加注意力机制,30多种模块分析⑦,CCN模块,GAMAttention模块

目录 一、注意力机制介绍1、什么是注意力机制&#xff1f;2、注意力机制的分类3、注意力机制的核心 二、CCN模块1、CCN模块的原理2、实验结果3、应用示例 三、GAMAttention模块1、GAMAttention模块的原理2、实验结果3、应用示例 大家好&#xff0c;我是哪吒。 &#x1f3c6;本…...

IDEA下Logback.xml自动提示功能配置

首先打开logback的配置文件&#xff0c;在configuration标签中加入xsd的配置 <configuration xmlns"http://ch.qos.logback/xml/ns/logback"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://ch.qos.logback/xml…...

CUDA编程模型系列八(原子操作 / 规约 / 向量元素求和)

本系列视频目的是帮助开发者们一步步地学会利用CUDA编程模型加速GPU应用, 我们的口号是: 让GPU飞起来 本期我介绍了cuda 当中规约算法的一种情况, 也是小何尚职业生涯中的第一道面试题, 计算数组中所有元素的和. CUDA编程模型系列八(原子操作 / 规约 / 向量元素求和) #include…...

go语言系列基础教程总结(4)

1、goroutine和channel 每执行一次go func()就创建一个 goroutine&#xff0c;包含要执行的函数和上下文信息。 goroutine 是Go程序并发的执行体&#xff0c;channel是它们之间的沟通连接通道。 var ch1 chan int. //声明一个整型的通道 2、channel 常用操作 //定义一个…...

网络基础一:网络协议初识与网络传输基本流程

目录 网络协议认识“协议”网络协议初识协议分层OSI七层模型&#xff08;理论模型&#xff09;TCP/IP五层(或四层)模型&#xff08;工程实现模型&#xff09; 网络中的地址管理MAC地址IP地址 网络传输基本流程路由的本质 数据包封装和分用网络协议需要解决的问题 网络协议 计算…...

Mysql找出执行慢的SQL【慢查询日志使用与分析】

分析慢SQL的步骤 慢查询的开启并捕获&#xff1a;开启慢查询日志&#xff0c;设置阈值&#xff0c;比如超过5秒钟的就是慢SQL&#xff0c;至少跑1天&#xff0c;看看生产的慢SQL情况&#xff0c;并将它抓取出来explain 慢SQL分析show Profile。&#xff08;比explain还要详细…...

设计模式3:单例模式:JMM与volatile和synchronized的关系

本文目录 JMM简介Java 内部内存模型(The Internal Java Memory Model)硬件内存架构(Hardware Memory Architecture)弥合 Java 内存模型和硬件内存架构之间的差距(Bridging The Gap Between The Java Memory Model And The Hardware Memory Architecture)1.共享对象的可见性2.竞…...

一个简单的OPC UA/ModbusTCP 网关(Python)

使用我前面几篇博文的内容&#xff0c;能够使用Python编写一个最简单的OPC UA /ModbusTCP网关。 从这个程序可以看出&#xff1a; 应用OPC UA 并不难&#xff0c;现在我们就可以应用到工程应用中&#xff0c;甚至DIY项目也可以。不必采用复杂的工具软件。使用Python 来构建工…...

线性代数行列式的几何含义

行列式可以看做是一系列列向量的排列&#xff0c;并且每个列向量的分量可以理解为其对应标准正交基下的坐标。 行列式有非常直观的几何意义&#xff0c;例如&#xff1a; 二维行列式按列向量排列依次是 a \mathbf{a} a和 b \mathbf{b} b&#xff0c;可以表示 a \mathbf{a} a和…...

python用flask将视频显示在网页上

注意我们的return返回值必须是以下之一&#xff0c;否则会报错 from flask import Flask, render_template, Response import cv2app Flask(__name__)app.route(/) def index():return render_template(index.html)def gen(camera):while True:success, image camera.read(…...

【数据挖掘】时间序列教程【一】

第一章 说明 对于时间序列的研究&#xff0c;可以追溯到19世纪末和20世纪初。当时&#xff0c;许多学者开始对时间相关的经济和社会现象进行研究&#xff0c;尝试发现其规律和趋势。其中最早的时间序列研究可以追溯到法国经济学家易贝尔&#xff08;Maurice Allais&#xff09;…...

优化索引粒度参数提升ClickHouse查询性能

当对高基数列进行过滤查询时&#xff0c;总是希望尽可能跳过更多的行。否则需要处理更多数据、需要更多资源。ClickHouse缺省在MergeTree表读取8192行数据块&#xff0c;但我们可以在创建表时调整该index_granularity 参数。本文通过示例说明如何调整该参数优化查询性能。 inde…...

selenium\webdriver\remote\errorhandler.py:242: SessionNotCreatedException问题解决

报错信息&#xff1a; raise exception_class(message, screen, stacktrace) E selenium.common.exceptions.SessionNotCreatedException: Message: session not created: This version of ChromeDriver only supports Chrome version 112 E Current browser versi…...

MySQL 备份与恢复

MySQL 备份与恢复 一、数据库备份的分类1.1 数据备份的重要性1.2 数据库备份的分类1.2.1 从物理与逻辑的角度&#xff0c;分为物理备份和逻辑备份1.2.2 从数据库的备份策略角度&#xff0c;分为完全备份&#xff0c;差异备份和增量备份1.2.3 常见的备份方法 二、MySQL完全备份与…...

js中改变this指向的三种方式

js中改变this指向的三种方式 1、call方法2、apply方法3、bind方法 1、call方法 使用 call 方法调用函数&#xff0c;同时指定函数中 this 的值&#xff0c;使用方法如下代码所示&#xff1a; <script>const obj {uname: 刘德华}function fn(x, y) {console.log(this) …...

小程序中如何进行数据传递和通信

103. 小程序中如何进行数据传递和通信&#xff1f; 1. 使用页面参数传递数据&#xff1a; 在小程序中&#xff0c;可以通过页面参数来传递数据。当跳转到一个新页面时&#xff0c;可以将需要传递的数据作为参数传入&#xff0c;然后在目标页面的onLoad函数中获取参数。 示例…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...