打家劫舍(LeetCode-198)

简介: 打家劫舍(LeetCode-198)

打家劫舍(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


思路

五部曲


dp[i]含义


偷窃前 i 个房子(包括房子i)可以获取的最大金额

递推公式


d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] )


数组初始化


dp[0]=0 dp[1]=nums[0]


遍历顺序


从前往后


代码

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]);
        }
        vector<int> dp(2);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        int result;
        for (int i = 2; i < n; i++)
        {
            result = max(dp[1], dp[0] + nums[i]);
            dp[0] = dp[1];
            dp[1] = result;
        }
        return result;
    }
};
目录
相关文章
|
编解码 算法 开发者
新手主播实战教程:YY开播工具+OBS美颜插件配置,零基础实现专业级直播画质
本文面向对直播画质有高要求的开发者与专业主播,详解如何通过YY开播工具的虚拟摄像头功能,将其美颜能力无缝集成至OBS推流软件,弥补OBS原生美颜功能的不足。内容涵盖软硬件准备、核心对接步骤及YY美颜参数调优技巧,帮助用户实现专业级直播视觉效果,同时提供常见问题解答,确保配置顺利。
新手主播实战教程:YY开播工具+OBS美颜插件配置,零基础实现专业级直播画质
|
数据库连接 API C#
WPF开发学生信息管理系统【WPF+Prism+MAH+WebApi】(二)(下)
WPF开发学生信息管理系统【WPF+Prism+MAH+WebApi】(二)(下)
408 0
|
1月前
|
人工智能 架构师 API
小微企业零成本搭建:Excel任务到期提醒工具的VBA自动推送系统(附保姆级教程)
职场中因忘记截止日期导致的项目延误屡见不鲜。本文剖析传统提醒方式的三大失效原因,测评五类智能任务提醒工具,并提供板栗看板等工具的实操方案,助你实现任务有迹可循、提醒精准到位,从“被动忘”转变为“主动追”。
小微企业零成本搭建:Excel任务到期提醒工具的VBA自动推送系统(附保姆级教程)
|
2月前
|
自然语言处理 前端开发 JavaScript
Playwright系列课(2) | 元素定位四大法宝:CSS/文本/XPath/语义化定位实战指南
本文是Playwright系列第二课,详解元素定位四大核心技术:CSS选择器、文本定位、XPath和语义化定位,结合实战演示各方法应用场景。重点解析Playwright智能定位器(Locator)的独特优势——自动等待与重试机制,通过预检元素可操作性(可见/可点击)有效规避网络延迟导致的脚本失效,显著提升自动化测试稳定性。
|
人工智能 分布式计算 DataWorks
首批!阿里云 MaxCompute 完成中国信通院数据智能平台专项测试
2024年5月31日,在中国信通院组织的首批数据智能平台专项测试中,阿里云数据智能平台解决方案(MaxCompute、DataWorks、PAI)顺利完成测试。
568 5
首批!阿里云 MaxCompute 完成中国信通院数据智能平台专项测试
|
Linux 数据处理 数据安全/隐私保护
Linux中的groups命令:管理用户组信息的利器
`groups`命令在Linux中用于显示用户所属的用户组,帮助管理员进行权限管理。它读取`/etc/group`和`/etc/passwd`文件获取信息,特点是简单直观,支持多用户组。命令参数如`-a`显示主组,`-g`显示主组ID,`-n`以数字形式显示,`-r`显示实际组。在实际应用中,结合其他命令可进行权限分析和定制输出。注意权限问题及用户组可能随系统变化。
|
11月前
|
监控 网络协议 安全
Linux系统日志管理
Linux系统日志管理
340 3
|
消息中间件 存储 网络协议
即时通讯需要用到哪些技术手段?
该文探讨了即时通讯技术,涉及网络协议(TCP/IP、UDP、HTTP/HTTPS)在IM中的应用,数据传输与同步(消息队列、长轮询、WebSocket、数据同步)技术,安全性保障(加密、认证授权、防止攻击)措施,以及多媒体处理(音频、视频处理和实时传输)和用户界面交互设计的重要性。文章旨在帮助读者理解并应用相关技术。
1131 1
|
编解码 网络协议 网络性能优化
RTP/RTCP 协议讲解
RTP/RTCP 协议讲解
1724 0
|
移动开发 小程序 安全
【社区每周】AIT现支持免登陆使用;小程序内嵌外跳H5页面支持支付宝端内官方应用(8月第一期)
【社区每周】AIT现支持免登陆使用;小程序内嵌外跳H5页面支持支付宝端内官方应用(8月第一期)
269 11