后端开发刷题 | 打家劫舍
描述
你是一个经验丰富的小偷,准备偷沿街的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家;如果偷了第二家,那么就不能偷第一家和第三家。
给定一个整数数组nums,数组中的元素表示每个房间存有的现金数额,请你计算在不被发现的前提下最多的偷窃金额。
数据范围:数组长度满足 1≤n≤2×105,数组中每个值满足 1≤num[i]≤5000
示例1
输入:
[1,2,3,4]
返回值:
6
说明:
最优方案是偷第 2,4 个房间
示例2
输入:
[1,3,6]
返回值:
7
说明:
最优方案是偷第 1,3个房间
示例3
输入:
[2,10,5]
返回值:
10
说明:
最优方案是偷第 2 个房间
思路分析:
该题使用动态规划来解决,
具体做法:
- step 1:用dp[i]表示长度为i的数组,最多能偷取到多少钱,只要每次转移状态逐渐累加就可以得到整个数组能偷取的钱。
- step 2:(初始状态) 如果数组长度为1,只有一家人,肯定是把这家人偷了,收益最大,因此dp[1]=nums[0]。
- step 3:(状态转移) 每次对于一个人家,我们选择偷他或者不偷他,如果我们选择偷那么前一家必定不能偷,因此累加的上上级的最多收益,同理如果选择不偷他,那我们最多可以累加上一级的收益。因此转移方程为dp[i]=max(dp[i−1],nums[i−1]+dp[i−2])。这里的i在dp中为数组长度,在nums中为下标。
图示:

代码:
import java.util.*;public class Solution {/*** @param nums int整型一维数组 * @return int整型*/public int rob (int[] nums) {int[] dp=new int[nums.length+1];dp[1]=nums[0];for(int i=2;i<=nums.length;i++){dp[i]=Math.max(dp[i-1],nums[i-1]+dp[i-2]);}return dp[nums.length];}
}
相关文章:
后端开发刷题 | 打家劫舍
描述 你是一个经验丰富的小偷,准备偷沿街的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家;如果偷了第二家࿰…...
欧美游戏市场的差异
欧洲和美国的游戏市场虽然高度发达且利润丰厚,但表现出由文化偏好、消费者行为、监管环境和平台受欢迎程度塑造的独特特征。这些差异对于寻求为每个地区量身定制策略的游戏开发商和发行商来说非常重要。 文化偏好和游戏类型 美国:美国游戏市场倾向于青…...
DeDeCMS靶场漏洞复现
打开靶场地址 姿势一:通过文件管理器上传webshell 1.登录后台 dedecms默认的后台登录地址为/dede 2.在附加管理里的文件式管理器中有文件上传 3.上传木马文件 4.访问木马文件 并连接 姿势二:修改模板文件获取webshell 1.点击模板里面的默认模板管理 …...
Transformer模型详细步骤
Transformer模型是nlp任务中不能绕开的学习任务,我将从数据开始,每一步骤都列举出来,然后对应重点的代码进行讲解 ------------------------------------------------------------------------------------------------------------- Trans…...
LC并联电路在正弦稳态下的传递函数推导(LC并联谐振选频电路)
LC并联电路在正弦稳态下的传递函数推导(LC并联谐振选频电路) 本文通过 1.解微分方程、2.阻抗模型两种方法推导 LC 并联选频电路在正弦稳态条件下的传递函数,并通过仿真验证不同频率时 vo(t) 与 vi(t) 的幅值相角的关系。 电路介绍 已知条件…...
【前后端】大文件切片上传
Ruoyi框架上传文件_若依微服务框架 文件上传-CSDN博客 原理介绍 大文件上传时,如果直接上传整个文件,可能会因为文件过大导致上传失败、服务器超时或内存溢出等问题。因此,通常采用文件切片(Chunking)的方式来解决这些…...
图像处理 -- ISP功能之局部对比度增强 LCE
局部对比度增强(LCE) 局部对比度增强(Local Contrast Enhancement, LCE)是一种图像处理技术,旨在通过调整图像的局部区域对比度,增强图像细节和视觉效果。LCE 的实现方式多种多样,以下是几种常…...
C++速通LeetCode简单第5题-回文链表
解法1,堆栈O(n)简单法: /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListN…...
【Java 优选算法】双指针(下)
欢迎关注个人主页:逸狼 创造不易,可以点点赞吗~ 如有错误,欢迎指出~ 有效三角形的个数 题目链接 解法 解法1:暴力枚举--->O(n^3) 解法2:利用单调性,使用双指针来解决---->O(n^2) 优化:对整个数组进行排序先固定最大数在最大数的左…...
动态规划:07.路径问题_珠宝的最大价值_C++
题目链接:LCR 166. 珠宝的最高价值 - 力扣(LeetCode)https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/ 一、题目解析 题目: 解析: 有过做前几道题的经验,我们会发现这道题其实就…...
COMDEL电源CX2500S RF13.56MHZ RF GENERATOR手侧
COMDEL电源CX2500S RF13.56MHZ RF GENERATOR手侧...
GPU加速生物信息分析的尝试
GPU工具分类 实话实说,暂时只有英伟达的GPU才能实现比较方便的基因组分析集成化解决方案,其他卡还需要努力呀,或者需要商业公司或学术团体的努力开发呀!FPGA等这种专用卡的解决方案也是有的,比如某测序仪厂家…...
【零散技术】详解Odoo17邮件发送(一)
序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo的邮件功能十分强大,在非常多的场景中可以看见其应用,例如原生的用户邀请,报价单发送,询价单发送等等.... 那么抛开原生自带的功能,我们如何巧妙的通过代码进行自…...
函数题 6-5 求自定类型元素的最大值【PAT】
文章目录 题目函数接口定义裁判测试程序样例输入样例输出样例 题解解题思路完整代码AC代码 编程练习题目集目录 题目 要求实现一个函数,求N个集合元素S[]中的最大值,其中集合元素的类型为自定义的ElementType。 函数接口定义 ElementType Max( Element…...
Python---爬虫
文章目录 目录 前言 一.Http请求/响应模块 requests模块 二.文本筛选模块 re模块 XPath模块 XPath 路径表达式 XPath 语法元素 三. 爬虫模板 爬虫案例 前言 Python爬虫是一种通过自动化程序爬取互联网上的信息的技术。爬虫可以自动访问网页并提取所需的数据,比…...
设计模式之组合设计模式
一、组合设计模式概念 组合模式 (Component) 是一种结构型设计模式,将对象组合成树形结构以表示“部分-整体”的层次结构。 组合模式使得用户对单个对象和组合对象的使用具有唯一性。 适用场景 想要表示对象的部分-整体层次结构。想要客户端忽略组合对象与单个对象的…...
Java汽车销售管理
技术架构: springboot mybatis Mysql5.7 vue2 npm node 有需要该项目的小伙伴可以添加我Q:598748873,备注:CSDN 功能描述: 针对汽车销售提供客户信息、车辆信息、订单信息、销售人员管理、财务报表等功能&…...
js TypeError: Cannot read property ‘initialize’ of undefined
js TypeError: Cannot read property ‘initialize’ of undefined 在JavaScript开发旅程中,遇到TypeError: Cannot read property ‘initialize’ of undefined这样的错误提示,无疑是令人沮丧的。这个错误通常意味着你试图访问一个未定义对象的initiali…...
【Motion Forecasting】【摘要阅读】BANet: Motion Forecasting with Boundary Aware Network
BANet: Motion Forecasting with Boundary Aware Network 这项工作发布于2022年,作者团队来自于OPPO。这项工作一直被放在arxiv上,并没有被正式发表,所提出的方法BANet在2022年达到了Argoverse 2 test dataset上的SOTA水准。 Method BANet…...
Cpp快速入门语法(下)(2)
文章目录 前言一、函数重载概念与使用C为何支持函数重载? 二、引用概念语法特性权限(常引用)使用场景与指针的区别 三、内联函数四、auto关键字(C11)五、基于范围的for循环(C11)六、指针空值nullptr(C11)总结 前言 承前启后,正文开始! 一、函…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
