53 打家劫舍

打家劫舍

    • 题解1 DP1
    • 题解2 DP2

!经典DP!
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果 两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警

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

示例 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

动态规划的的四个解题步骤是:

  1. 定义子问题: 总问题:抢N个房子 – > 子问题:抢 K个房子

  2. 写出子问题的递推关系:第k个房子要么被抢要么不被抢:F(k) = max(F(k-1), nums[k] + F(k-2))
    (只与前两个房子的最大金额有关——空间优化,N长数组变成2个变量)在这里插入图片描述

  3. 确定 DP 数组的计算顺序
    动态规划有两种计算顺序,一种是自顶向下的、使用备忘录的递归方法,一种是自底向上的、使用 dp 数组的循环方法。不过在普通的动态规划题目中,99% 的情况我们都不需要用到备忘录方法,所以我们最好坚持用自底向上的 dp 数组
    DP 数组中的依赖关系都是向右指的,DP 数组的计算顺序就是从左向右。这样我们可以保证,计算一个子问题的时候,它所依赖的那些子问题已经计算出来了。
    在这里插入图片描述

  4. 空间优化(可选)

题解1 DP1

class Solution {
public:int rob(vector<int>& nums) {int s = nums.size();vector<int> dp(s+1, 0);dp[1] = nums[0];for(int i = 1; i < s; i++){dp[i+1] = max(dp[i], dp[i-1]+nums[i]);}return dp[s];}
};

在这里插入图片描述

题解2 DP2

class Solution {
public:int rob(vector<int>& nums) {int s = nums.size();if(1 == s) return nums[0];int first = nums[0];int sec = max(nums[0], nums[1]);for(int i = 2; i < s; i++){int tmp = sec;// sec是i-1的情况, first是i-2sec = max(first+nums[i], sec);first = tmp;}return sec;}
};

在这里插入图片描述

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

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

相关文章

【C++】继承 -- 详解

一、继承的概念及定义 1、继承的概念 继承 (inheritance) 机制是面向对象程序设计使代码可以复用的最重要的手段&#xff0c;它允许程序员在保 持原有类特性的基础上进行扩展&#xff0c;增加功能&#xff0c;这样产生新的类&#xff0c;称派生类。 继承呈现了面向对象 程序设…

【Vue】vue2与netcore webapi跨越问题解决

系列文章 C#底层库–记录日志帮助类 本文链接&#xff1a;https://blog.csdn.net/youcheng_ge/article/details/124187709 文章目录 系列文章前言一、技术介绍二、问题描述三、问题解决3.1 方法一&#xff1a;前端Vue修改3.2 方法二&#xff1a;后端允许Cors跨越访问 四、资源…

前端TypeScript学习day04-交叉类型与泛型

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 交叉类型 泛型 创建泛型函数 调用泛型函数&#xff1a; 简化调用泛型函数&#xff1a; 泛型约束 指定…

浅谈MDK, IAR,CLANG和GCC的局部变量字节对齐处理差异(2023-10-13)

视频&#xff1a; https://www.bilibili.com/video/BV1CB4y1Z7kA 浅谈MDK, IAR, CLANG和GCC的局部变量字节对齐处理差异 问题由来&#xff1a; 早期这个帖子里面的局部变量对齐仅测试了MDK AC5&#xff0c;但项目中使用AC6发现了新问题&#xff0c;看来AAPCS规约研究的还是不…

centos 里面的service自启动app.jar,出现两个java进程,app是同一个端口

当使用jps -lv查看java虚拟机进程 app.jar启动后&#xff0c;居然出现两个启动进程&#xff0c;而且他们的端口都一样&#xff0c;同一端口&#xff0c;是不允许启动两个相同app的。 使用进程ps查看进程工具 #ps -aux 参数说明&#xff1a; a: 显示跟当前终端关联的所有进…

《Deep Residual Learning for Image Recognition》阅读笔记

论文标题 《Deep Residual Learning for Image Recognition》 撑起CV界半边天的论文Residual &#xff1a;主要思想&#xff0c;残差。 作者 何恺明&#xff0c;超级大佬。微软亚研院属实是人才辈出的地方。 初读 摘要 提问题&#xff1a; 更深层次的神经网络更难训练。 …

PHP基础语法(上)

目录 前言 一、基础语法 1.1 标记 1.2 输出语句 1.2.1 echo 1.2.2 print 1.3 注释 1.3.1 单行注释 1.3.2 多行注释 1.4 标识符 1.5 关键字 二、数据与运算 2.1 常量 2.1.1 常量的定义和使用 2.1.2 预定义常量 2.2 变量 2.2.1 变量的赋值 2.2.2 超全局变量 2.3 数据类型 2.3.1 …

Nginx:反向代理(示意图+配置)

示意图&#xff1a; 反向代理 反向代理&#xff08;Reverse Proxy&#xff09;是代理服务器的一种&#xff0c;它代表服务器接收客户端的请求&#xff0c;并将这些请求转发到适当的服务器。当请求在后端服务器完成之后&#xff0c;反向代理搜集请求的响应并将其传输给客户端。…

Tableau:商业智能(BI)工具

Tableau入门 1、Tableau概述2、Tableau Desktop2.1、初识Tableau Desktop2.2、Tableau工作区2.3、数据窗格与分析窗格2.4、功能区和标记卡2.4.1、列和行功能区2.4.2、标记卡2.4.3、筛选器功能区2.4.4、页面功能区2.4.5、附加功能区、图例、控件 3、Tableau视图4、Tableau工作簿…

LeetCode讲解篇之198. 打家劫舍

LeetCode讲解篇之198. 打家劫舍 文章目录 LeetCode讲解篇之198. 打家劫舍题目描述题解思路题解代码 题目描述 题解思路 该问题可以通过递推来完成 递推公式&#xff1a; 前n间房的最大金额 max&#xff08;前n-1间房的最大金额&#xff0c; 前n-2间房的最大金额第n-1间房的最…

Hadoop2.0探讨

文章目录 8. Hadoop 再探讨8.1 Hadoop的优化与发展8.2 HDFS 的FA和Federation(Hadoop2.0新特性)8.2.1 HDFS HA8.2.2 HDFS Federation 8.3 YARN8.3.1 MapReduce1.0的缺陷8.3.2 Yarn设计思路8.3.3 Yarn体系结构8.3.4 Yarn工作流程8.3.5 Yarn框架和MapReduce1.0框架对比分析8.3.6 …

asp.net酒店餐饮管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net酒店餐饮管理系统是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言 开发 ASP.NE 酒店餐饮管理系统 二、功能…

AMD AFMF不但能用在游戏,也适用于视频

近期AMD发布了AMD Software Adrenalin Edition预览版驱动程序&#xff0c;增加了对平滑移动帧&#xff08;AMD Fluid Motion Frames&#xff0c;AFMF&#xff09;功能的支持&#xff0c;也就是AMD的“帧生成”技术&#xff0c;与DLSS 3类似&#xff0c;作为FidelityFX Super Re…

毅速丨模具3D打印材料有哪些选择

当前1.2709和CX是市面上最常用的3D打印模具钢材料&#xff0c;模具3D打印有没有更多的材料选择呢&#xff1f; 据了解&#xff0c;上海毅速推出的几款3D打印新材料正在被越来越多的行业所采用。如毅速的EM191S高性能高抛光不锈钢粉末&#xff0c;这款材料的抗开裂和耐腐蚀性能是…

LeetCode【240】搜索二维矩阵

题目&#xff1a; 思路&#xff1a; 1、单靠对角线元素无法判定位置 2、主要逐行进行二分 代码&#xff1a; public boolean searchMatrix(int[][] matrix, int target) {int rows matrix.length;int columns matrix[0].length;// 按行进行二分for (int i 0; i < rows…

与HTTP相关的各种概念

网络世界 网络世界中最重要的一个名词就是互联网&#xff08;Internet&#xff09;,它以TCP/IP协议族为基础&#xff0c;构建成了一望无际的信息传输网络。而我们通常所说的“上网”&#xff0c;主要就是访问互联网的一个子集——万维网&#xff08;World Wide Web&#xff09…

MDK自动生成带校验带SVN版本号的升级文件

MDK自动生成带校验带SVN版本号的升级文件 获取SVN版本信息 确保SVN安装了命令行工具&#xff0c;默认安装时不会安装命令行工具 编写一个模板头文件 svn_version.temp.h, 版本号格式为 1_0_0_SVN版本号 #ifndef __SVN_VERSION_H #define __SVN_VERSION_H#define SVN_REVISIO…

网络-HTTPS

文章目录 前言一、HTTPS简介优点SSL/TSL工作流程 加密1、对称加密2、非对称加密 二、使用HTTPS1.openSSL生成私钥&#xff08;1&#xff09;node服务端&#xff08;2&#xff09;nginx配置https服务&#xff08;前端&#xff09; nginx服务 总结 前言 Http 存在不安全、无状态…

[数据结构]——单链表超详细总结

带你走进链表的世界 目录&#xff1a;一、线性表的概念二、顺序表三、链表3.1 链表的概念3.2 链表的分类3.3 无头单向非循环链表的实现3.4 带头双向循环链表的实现 四、顺序表和链表的区别和联系 目录&#xff1a; 链表是个优秀的结构&#xff0c;没有容量概念&#xff0c;可以…

基于PHP的芒果销售交易平台

有需要请加文章底部Q哦 可远程调试 基于PHP的芒果销售交易平台 一 介绍 芒果销售交易平台基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。用户可注册登录&#xff0c;购物下单&#xff0c;评论等。管理员登录后台可对芒果&#xff0c;用户&#xff0c;订…