【动态规划-BM78 打家劫舍(一)】

题目

描述
你是一个经验丰富的小偷,准备偷沿街的一排房间,每个房间都存有一定的现金,为了防止被发现,你不能偷相邻的两家,即,如果偷了第一家,就不能再偷第二家;如果偷了第二家,那么就不能偷第一家和第三家。
给定一个整数数组nums,数组中的元素表示每个房间存有的现金数额,请你计算在不被发现的前提下最多的偷窃金额。

在这里插入图片描述

分析

可以使用动态规划的原因:考虑前i家能获得的最多金额可以由前i-1 或者i-2家获得

dp[i]: 在考虑前i家的情况下能够获得的最多金额

当不偷第i家时,dp[i]=dp[i-1]
当偷第i家时,dp[i] = dp[i-2] + nums[i-1]
取两者最大值即可

当只有一家时,一定偷,所以dp[1]=nums[0]

代码

class Solution:def rob(self , nums: List[int]) -> int:# write code heren = len(nums)# dp[i]:考虑前i家能够获得的最多金额dp = [0]*(n+1)dp[1] = nums[0]for i in range(2, n+1):dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])return dp[n]

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

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

相关文章

WPS JS宏获取自动筛选后的行数

//WPS JS宏获取自动筛选后的行数 function getFilterRowCnt(shtRng)//shtRng表示筛选目标工作表范围 {let lngRowCnt 0;for(let rngCell of shtRng.SpecialCells(xlCellTypeVisible).Areas)//获取自动筛选后的单元格行数{lngRowCnt lngRowCnt rngCell.Rows.Count;}return ln…

【ARM Cache 及 MMU 系列文章 6.3 -- ARMv8/v9 Cache Tag数据读取及分析】

请阅读【ARM Cache 及 MMU/MPU 系列文章专栏导读】 及【嵌入式开发学习必备专栏】 文章目录 Cache Tag 数据读取测试代码Cache Tag 数据读取 在处理器中,缓存是一种快速存储资源,用于减少访问主内存时的延迟。缓存通过存储主内存中经常访问的数据来实现这一点。为了有效地管…

【JavaScript】内置对象 - 字符串对象 ⑤ ( 判断对象中是否有某个属性 | 统计字符串中每个字符出现的次数 )

文章目录 一、判断对象中是否有某个属性1、获取对象属性2、判定对象是否有某个属性 二、统计字符串中每个字符出现的次数1、算法分析2、代码示例 String 字符串对象参考文档 : https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/String 一、判…

车载诊断架构 - 引导诊断

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…

2024年几款优秀的SQL IDE优缺点分析

SQL 工具在数据库管理、查询优化和数据分析中扮演着重要角色。 以下是常见的 SQL 工具及其优缺点。 1. SQLynx 优点: 智能代码补全和建议:采用AI技术提供高级代码补全、智能建议和自动错误检测,大幅提高编写和调试SQL查询的效率。跨平台和…

MFC 教程-回车时窗口退出问题

【问题描述】 MFC窗口默认时,按回车窗口会退出 【原因分析】 默认调用OnOK() 【解决办法】 重写虚函PreTranslateMessage BOOL CTESTMFCDlg::PreTranslateMessage(MSG* pMsg) {// TODO: 在此添加专用代码和/或调用基类// 修改回车键的操作反应 if (pMsg->…

扩散模型条件生成——Classifier Guidance和Classifier-free Guidance原理解析

1、前言 从讲扩散模型到现在。我们很少讲过条件生成(Stable DIffusion曾提到过一点),所以本篇内容。我们就来具体讲一下条件生成。这一部分的内容我就不给原论文了,因为那些论文并不只讲了条件生成,还有一些调参什么的…

学习笔记——路由网络基础——静态路由(static)

三、静态路由(static) 1、静态路由 (1)定义 静态路由(Static):由管理员手动配置和维护的路由。静态路由配置简单,被广泛应用于网络中。此外还可以实现负载均衡和路由备份。 静态路由默认优先级为60,如果想在多条静态路由中让某条路由优选…

Unity基础实践小项目

项目流程: 需求分析 开始界面 选择角色面板 排行榜面板 设置面板 游戏面板 确定退出面板 死亡面板 UML类图 准备工作 1.导入资源 2.创建需要的文件夹 3.创建好面板基类 开始场景 开始界面 1.拼面板 2.写脚本 注意事项:注意先设置NGUI的分辨率大小&…

Scala 练习一 将Mysql表数据导入HBase

Scala 练习一 将Mysql表数据导入HBase 续第一篇:Java代码将Mysql表数据导入HBase表 源码仓库地址:https://gitee.com/leaf-domain/data-to-hbase 一、整体介绍二、依赖三、测试结果四、源码 一、整体介绍 HBase特质 连接HBase, 创建HBase执行对象 初始化…

从0到1:企业办公审批小程序开发笔记

可行性分析 企业办公审批小程序,适合各大公司,企业,机关部门办公审批流程,适用于请假审批,报销审批,外出审批,合同审批,采购审批,入职审批,其他审批等规划化…

使用 stress 命令进行Linux CPU 压力测试

大家好,在现代计算机系统中,对系统性能和稳定性的评估是至关重要的。特别是在服务器环境中,我们需要确保系统能够在高负载情况下稳定运行,以满足用户的需求。而 CPU 是系统中最关键的组件之一,其性能直接影响着整个系统…

用 DataGridView 控件显示数据

使用DataGridView,可以很方便显示数据。 (1)Visual Studio版本:Visual Studio 2022 (2)应用程序类型:windows form (3)编程语言:C# 一、目标框架 .NET Fra…

【NI国产替代】高速数据采集模块,最大采样率为 125 Msps,支持 FPGA 定制化

• 双通道高精度数据采集 • 支持 FPGA 定制化 • 双通道高精度采样率 最大采样率为 125 Msps12 位 ADC 分辨率 最大输入电压为 0.9 V -3 dB 带宽为 30 MHz 支持 FPGA 定制化 根据需求编程实现特定功能和性能通过定制 FPGA 实现硬件加速,提高系统的运算速度FPGA…

Docker中搭建likeadmin

一、使用Docker中的docker-compose搭建likeadmin 1.去网址:https://gitee.com/likeadmin/likeadmin_php中下载likeadmin 注册一个giee账号后 点那个克隆下载 按照序号在终端复制粘贴进去。 接着,输入ls 可以发现有一个这个: 里面有一个like…

服务器数据恢复—服务器raid5上层zfs文件系统数据恢复案例

服务器数据恢复环境&故障: 一台某品牌X3650M3服务器,服务器中有一组raid5磁盘阵列,上层采用zfs文件系统。 服务器未知原因崩溃,工作人员排查故障后发现服务器的raid5阵列中有两块硬盘离线导致该阵列不可用,服务器内…

Cell-在十字花科植物中年生和多次开花多年生开花行为的互相转化-文献精读21

Reciprocal conversion between annual and polycarpic perennial flowering behavior in the Brassicaceae 在十字花科植物中年生和多次开花多年生开花行为的互相转化 亮点 喜马拉雅须弥芥 和 内华达糖芥 是两个多年生植物模型 MADS-box 基因的剂量效应决定了一年生、二年生…

NodeJs实现脚本:将xlxs文件输出到json文件中

文章目录 前期工作和依赖笔记功能代码输出 最近有一个功能,将json文件里的内容抽取到一个xlxs中,然后维护xlxs文件。当要更新json文件时,就更新xlxs的内容并把它传回json中。这个脚本主要使用NodeJS写。 以下是完成此功能时做的一些笔记。 …

Oracle EBS AP发票创建会计科目错误:子分类帐日记帐分录未按输入币种进行平衡

系统版本 RDBMS : 12.1.0.2.0 Oracle Applications : 12.2.6 问题症状: 提交“创建会计科目”请求提示错误信息如下: 中文报错: 该子分类帐日记帐分录未按输入币种进行平衡。请检查日记帐分录行中输入的金额。 英文报错:The subledger journal entry does not balance i…

11 IP协议 - IP协议头部

什么是 IP 协议 IP(Internet Protocol)是一种网络通信协议,它是互联网的核心协议之一,负责在计算机网络中路由数据包,使数据能够在不同设备之间进行有效的传输。IP协议的主要作用包括寻址、分组、路由和转发数据包&am…