leetcode198打家劫舍

题目描述

LeetCode 第 198 题——打家劫舍(House Robber)

你是一个职业小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,这个地方所有的房屋都围成一圈,并且相邻的房屋有安全系统会相连,如果两间相邻的房屋在同一晚上被打劫,系统会自动报警。

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

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

解题思路

这道题可以看作是一个斐波那契数列问题。因为要到达第 n 阶楼梯的方法数量等于到达第 n-1 阶楼梯和到达第 n-2 阶楼梯的方法数量之和。
具体来说:
到达第 n 阶楼梯的方法 = 到达第 n-1 阶楼梯的方法 + 到达第 n-2 阶楼梯的方法。
当 n=1 时,只有一种方法。
当 n=2 时,有两种方法。
因此,我们可以用动态规划来解决这个问题,使用一个数组或两个变量来存储到达每一阶楼梯的方法数量。

解题步骤

1.判断 n 是否小于或等于 2,如果是,直接返回 n。
2.初始化两个变量 a 和 b 分别代表到达 n-2 和 n-1 阶楼梯的方法数量,并设定初始值为 1 和 2。
3.从 3 开始遍历到 n,每一步更新 a 和 b 的值,b 的新值为 a 和 b 之和,而 a 的新值为原先 b 的值。
4.返回 b 的值,即为最终的答案。

具体步骤

1.如果房屋数量为 0,直接返回 0。
2.如果房屋数量为 1,直接返回该房屋的金额。
3.初始化一个长度为 n 的数组 dp,其中 dp[i] 表示到达第 i 间房屋时能够偷窃到的最高金额。
4.dp[0] 初始化为第一个房屋的金额,dp[1] 初始化为 max(nums[0], nums[1]),表示前两个房屋中金额较大者。
5.从第 2 间房屋开始,通过递推公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 计算出每间房屋能够偷窃到的最高金额。
6.返回 dp[n-1] 作为最终结果,即为到达最后一个房屋时能够偷窃到的最高金额。

代码实现

func rob(nums []int) int {n := len(nums)// 如果房屋数量为 0,直接返回 0if n == 0 {return 0}// 如果房屋数量为 1,直接返回该房屋的金额if n == 1 {return nums[0]}// 初始化动态规划数组 dpdp := make([]int, n)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])// 初始化第一个房屋和前两个房屋的最大偷窃金额for i := 2; i < n; i++ {dp[i] = max(dp[i-1], dp[i-2]+nums[i])}// 返回最后一个房屋的最高偷窃金额return dp[n-1]
}// max 函数返回两个整数中的最大值
func max(a, b int) int {if a > b {return a}return b
}

代码测试

func main() {// 测试用例testCases := [][]int{{1, 2, 3, 1},{2, 7, 9, 3, 1},{2, 1, 1, 2},{5, 3, 4, 11, 2},}// 遍历测试用例并输出结果for _, nums := range testCases {fmt.Printf("房屋金额: %v, 最高偷窃金额: %d\n", nums, rob(nums))}
}

测试结果

在这里插入图片描述

关于题目疑问

Q1 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 这个递推公式是怎么算出来的

我们要解决的问题是:在一排房屋中,小偷不能同时偷窃相邻的两间房屋,求能偷窃到的最大金额。
假设我们已经计算到了第 i 间房屋,面临两个选择:
不偷第 i 间房屋:那么小偷能获得的最大金额就是前一间房屋的最大偷窃金额,即 dp[i-1]。
偷第 i 间房屋:由于不能偷相邻的房屋,因此小偷只能选择从第 i-2 间房屋开始偷,这时的最大偷窃金额为 dp[i-2],再加上第 i 间房屋的金额 nums[i],总金额为 dp[i-2] + nums[i]。

递推公式推导:
基于上面的分析,我们可以得出:
如果小偷选择不偷第 i 间房屋,最大金额为 dp[i-1]。
如果小偷选择偷第 i 间房屋,最大金额为 dp[i-2] + nums[i]。
为了保证小偷获得的总金额最大,我们在这两种选择中取较大值
dp[i] = max(dp[i-1], dp[i-2] + nums[i])

总结

dp[i] 的值取决于是否选择偷窃当前的房屋 i,以及偷窃之前房屋的情况。
递推公式 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 就是基于这两种选择所能获得的最大金额计算出来的。
最终,dp[n-1] 就是小偷在 n 间房屋内所能获得的最大金额。

Q2 什么是动态规划?

动态规划(Dynamic Programming,简称 DP)是一种算法设计技巧,用于解决具有重叠子问题和最优子结构性质的问题。它的核心思想是通过将问题分解为更小的子问题,逐步求解并保存这些子问题的解,从而构建出原问题的解。动态规划通常用于优化问题,尤其是那些存在多种可能选择或路径的问题。

例子分析
举例来说,abb 和 egg 是同构的,因为可以通过如下映射来匹配:
a -> e
b -> g
这意味着字符串 s 中的每个字符都可以找到一个对应的字符 t,并且这个映射在整个字符串中是一致的。

动态规划核心思想

重叠子问题:
问题可以被分解为多个子问题,这些子问题之间存在重叠,也就是说,同一个子问题会被多次计算。
例如,在计算斐波那契数列时,F(n) = F(n-1) + F(n-2),其中 F(n-1) 和 F(n-2) 是重复计算的子问题。
最优子结构:
一个问题的最优解可以通过其子问题的最优解组合而成。
例如,在最短路径问题中,找到从起点到终点的最短路径可以通过找到从起点到某个中间节点的最短路径,再加上从该中间节点到终点的最短路径来实现。
状态转移方程:
动态规划通过状态转移方程来表示问题的递推关系。这个方程通常是基于问题的最优子结构性质来构建的。
例如,在打家劫舍问题中,状态转移方程是 dp[i] = max(dp[i-1], dp[i-2] + nums[i]),表示到第 i 间房屋时的最大偷窃金额。
存储中间结果:
为了避免重复计算,动态规划会存储已经计算过的子问题的结果,通常使用数组或表来保存这些中间结果。
例如,在计算斐波那契数列时,可以用一个数组来存储每一个 F(n) 的值,避免重复计算。

动态规划步骤

1.定义状态:确定如何表示问题的子问题,通常使用一个数组或表格来表示不同状态。例如,在打家劫舍问题中,dp[i] 表示从第 0 到第 i 间房屋的最大偷窃金额。
2.构建状态转移方程:根据问题的最优子结构,确定如何从一个状态转移到另一个状态。例如,在打家劫舍问题中,状态转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
3.初始化:为状态数组或表格设定初始值。例如,斐波那契数列中,F(0) 和 F(1) 需要被初始化为 0 和 1。
4.计算并填表:根据状态转移方程,从初始状态开始逐步计算出所有的状态。
5.输出结果:最后输出表格中保存的最终结果。

总结

动态规划是一种非常强大的算法设计方法,适用于解决优化类问题,特别是那些具有重叠子问题和最优子结构的场景。它通过逐步解决子问题并存储结果来避免重复计算,从而显著提高了效率。

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

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

相关文章

【C++高阶】哈希—— 位图 | 布隆过滤器 | 哈希切分

✨ 人生如梦&#xff0c;朝露夕花&#xff0c;宛若泡影 &#x1f30f; &#x1f4c3;个人主页&#xff1a;island1314 &#x1f525;个人专栏&#xff1a;C学习 ⛺️ 欢迎关注&#xff1a;&#x1f44d;点赞 &#x1f442;&am…

C++竞赛初阶L1-11-第五单元-for循环(25~26课)519: T454430 人口增长问题

题目内容 假设目前的世界人口有 x 亿&#xff0c;按照每年 0.1% 的增长速度&#xff0c;n 年后将有多少人&#xff1f; 输入格式 一行两个正整数 x 和 n&#xff0c;之间有一个空格。其中&#xff0c;1≤x≤100,1≤n≤100。 输出格式 一行一个数&#xff0c;表示答案。以亿…

RK3576 芯片介绍

RK3576 芯片介绍 RK3576瑞芯微第二代8nm高性能AIOT平台&#xff0c;它集成了独立的6TOPS&#xff08;Tera Operations Per Second&#xff0c;每秒万亿次操作&#xff09;NPU&#xff08;神经网络处理单元&#xff09;&#xff0c;用于处理人工智能相关的任务。此外&#xff0…

使用ITextRenderer导出PDF后无法打开问题,提示‘无法打开此文件‘

依赖如下 <!-- https://mvnrepository.com/artifact/org.xhtmlrenderer/flying-saucer-pdf --> <dependency><groupId>org.xhtmlrenderer</groupId><artifactId>flying-saucer-pdf</artifactId><version>9.1.22</version> &l…

6.MySQL的增删改查

目录 Create 单行插入数据 全列插入 多行数据指定列插入 插入否则更新 主键冲突 唯一键冲突 &#xff08;☆&#xff09; 替换数据 Retrieve Select列 全列查询 指定列查询 查询字段为表达式 where条件 NULL 的查询 NULL 和 NULL 的比较&#xff0c; 和 <>…

如何选择图片和视频

文章目录 1. 概念介绍2. 方法与细节2.1 实现方法2.2 具体细节 3. 示例代码4. 内容总结 我们在上一章回中介绍了"如何选择视频文件"相关的内容&#xff0c;本章回中将介绍如何混合选择图片和视频文件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 1. 概念介绍 我…

Vue3学习 Day01

创建第一个vue项目 1.安装node.js cmd输入node查看是否安装成功 2.vscode开启一个终端&#xff0c;配置淘宝镜像 # 修改为淘宝镜像源 npm config set registry https://registry.npmmirror.com 输入如下命令创建第一个Vue项目 3.下载依赖&#xff0c;启动项目 访问5173端口 …

在线考试系统源码开发

在线考试系统开发需求与功能架构概览可以归纳为以下几个方面&#xff1a; 一、系统开发需求&#xff1a; 1、安全保障&#xff1a;系统需要提供完善的安全措施&#xff0c;这包括但不限于用户身份验证、数据加密技术&#xff0c;以及防止作弊的功能&#xff0c;确保考试的公平…

C语言程序设计-[23] 数组应用(续)

1、输入一行字符,统计其中有多少个单词。 根据以上分析&#xff0c;代码与结果如下&#xff1a; #include "stdio.h"int main ( ) { char c,pre,str[81];int i, n0;gets (str);pre ;for (i0; cstr[i]; i){if (c ! && pre ){ n;}pre c;}printf("…

谷歌发布会回顾:Gemini Live 与 Pixel 9 系列重磅亮相!

在 2024 年的 Made by Google 大会 上&#xff0c;谷歌重磅发布了全新 AI 产品 Gemini Live 和新一代硬件设备 Pixel 9 系列。这场发布会的亮点不只是 AI 的进步&#xff0c;还在于其硬件与 AI 的深度融合。本文将从技术角度回顾此次发布的重点内容&#xff0c;深入解析 Gemini…

Python爬虫——爬取某网站的视频

爬取视频 本次爬取&#xff0c;还是运用的是requests方法 首先进入此网站中&#xff0c;选取你想要爬取的视频&#xff0c;进入视频播放页面&#xff0c;按F12&#xff0c;将网络中的名称栏向上拉找到第一个并点击&#xff0c;可以在标头中&#xff0c;找到后续我们想要的一些…

WebGIS开发中一些常见的概念

0. 坐标系投影 地理坐标系和投影坐标系是两种常用的坐标系统&#xff0c;它们各自有着独特的特性和应用场景。 0.1 地理坐标系 地理坐标系(Geographic Coordinate System&#xff0c; 简称 GCS)是以地球椭球体面为参考面&#xff0c;以法线为依据&#xff0c;用经纬度表示地…

Knowledge-Adaptive Contrastive Learning for Recommendation

Knowledge-Adaptive Contrastive Learning for Recommendation&#xff08;WSDM2023&#xff09; 摘要 通过对用户-项目交互和知识图&#xff08;KG&#xff09;信息进行联合建模&#xff0c;基于知识图谱的推荐系统在缓解数据稀疏和冷启动问题方面表现出了优越性。 近年来&a…

C++中STL的sring类常用接口及其源码解析

1. 为什么会有string类&#xff1f; C语言中的字符串 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c; 但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP的思想&#xff0…

基于Mysql的商业辅助决策系统的设计与实现

TOC springboot295基于Mysql的商业辅助决策系统的设计与实现 第1章 绪论 1.1 课题背景 二十一世纪互联网的出现&#xff0c;改变了几千年以来人们的生活&#xff0c;不仅仅是生活物资的丰富&#xff0c;还有精神层次的丰富。在互联网诞生之前&#xff0c;地域位置往往是人们…

机器学习/深度学习——关于分类任务的机器学习、深度学习模型的评估指标详解

机器学习/深度学习——模型的评估详解 搭配以下文章进行学习&#xff1a; 卷积神经网络&#xff1a; 深度学习——卷积神经网络&#xff08;convolutional neural network&#xff09;CNN详解&#xff08;一&#xff09;——概述. 步骤清晰0基础可看 深度学习——卷积神经网…

virtualbox 安装 win7 系统注意事项

win7可用ISO镜像 virtualbox安装Windows 7 64位旗舰版 &#xff08;包含镜像文件&#xff09;_virtual pc安装64位windows7-CSDN博客 视图设为了自动缩放&#xff0c;没有菜单了怎么办&#xff1f; 通过按右侧CtrlC/F/L进行切换 复制黏贴不公用怎么办&#xff1f; 宿主机有…

Word密码忘记怎么办?三个密码找回工具帮你轻松找回密码

在工作当中&#xff0c;为了保护文档内容的安全&#xff0c;我们时常会设置密码。但有时会因为长时间未打开而忘记了密码&#xff0c;导致word文档无法打开。面对这种情况&#xff0c;我们该怎么办呢&#xff1f;下面小编就将给大家带来3个实用的密码找回工具&#xff0c;帮助大…

XSS游戏前五关

分享一个XSS游戏的链接 XSS Game 第一关&#xff1a; 这边有一个innerHTML属性&#xff0c;我们查看官方文档 我们找到了它存在的漏洞&#xff0c;直接利用 https://sandbox.pwnfunction.com/warmups/ma-spaghet.html?somebody<img src1 onerror"alert(1337)&quo…

人工智能在子宫内膜癌领域的研究进展|顶刊速递·24-08-12

小罗碎碎念 本期推文主题&#xff1a;人工智能在子宫内膜癌领域中的研究进展 昨天的推文主要介绍的是卵巢癌&#xff0c;有一小部分涉及到了子宫内膜癌&#xff0c;按照最新的规划&#xff0c;今天的推文是与子宫内膜癌相关的。 从事妇科肿瘤研究的老师/同学&#xff0c;可以好…