打家劫舍(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;
    }
};
目录
打赏
0
0
0
0
3
分享
相关文章
kde
|
5天前
|
Docker镜像加速指南:手把手教你配置国内镜像源
配置国内镜像源可大幅提升 Docker 拉取速度,解决访问 Docker Hub 缓慢问题。本文详解 Linux、Docker Desktop 配置方法,并提供测速对比与常见问题解答,附最新可用镜像源列表,助力高效开发部署。
kde
3152 8
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
国内如何安装和使用 Claude Code镜像教程 - Windows 用户篇
572 0
Dify MCP 保姆级教程来了!
大语言模型,例如 DeepSeek,如果不能联网、不能操作外部工具,只能是聊天机器人。除了聊天没什么可做的。
842 9
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
【保姆级图文详解】大模型、Spring AI编程调用大模型
【保姆级图文详解】大模型、Spring AI编程调用大模型
359 7
【保姆级图文详解】大模型、Spring AI编程调用大模型
Excel数据治理新思路:引入智能体实现自动纠错【Python+Agent】
本文介绍如何利用智能体与Python代码批量处理Excel中的脏数据,解决人工录入导致的格式混乱、逻辑错误等问题。通过构建具备数据校验、异常标记及自动修正功能的系统,将数小时的人工核查任务缩短至分钟级,大幅提升数据一致性和办公效率。
DeepSeek R1+Open WebUI实现本地知识库的搭建和局域网访问
本文介绍了使用 DeepSeek R1 和 Open WebUI 搭建本地知识库的详细步骤与注意事项,涵盖核心组件介绍、硬件与软件准备、模型部署、知识库构建及问答功能实现等内容,适用于本地文档存储、向量化与检索增强生成(RAG)场景的应用开发。
369 0
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
阿里云推出基于场景的解决方案免费试用活动,新老用户均可领取100点试用点,完成部署还可再领最高100点,相当于一年可获得最高200元云资源。覆盖AI、大数据、互联网应用开发等多个领域,支持热门场景如DeepSeek部署、模型微调等,助力企业和开发者快速验证方案并上云。
306 22
让AI时代的卓越架构触手可及,阿里云技术解决方案开放免费试用
FLUX.1 Kontext 的全生态教程来啦!AIGC专区在线试玩!
Flux.1 Kontext [dev] 开源模型大家都用上了吗?小编汇总了3个使用教程,打包送上!
426 1
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等