LeetCode算法心得——打家劫舍(记忆化搜索)

大家好,我是晴天学长,准备开始深入动态规划啦,先从记忆化搜索开始,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪


1) .打家劫舍

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

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

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

提示:

1 <= nums.length <= 100
0 <= nums[i] <= 400


2) .算法思路

  • 纯dfs也可以,但是会超时。
  • 所以用到了记忆化搜索。
  • 用一个数组简单的记录搜索的答案进行返回。
  • 只关注现在的状态和上一步的状态。

3) .算法步骤

1.定义一个私有的数组 nums 和 memo,用于存储输入的房屋金额和记忆化搜索的结果。
2.创建 rob 方法来启动算法。在该方法中,初始化 nums 和 memo 数组,并将 memo 数组的所有元素初始化为 -1。
3.调用 dfs 方法,将起始索引设为 nums.length - 1(最后一个房屋),并返回结果。
4.在 dfs 方法中,首先检查是否已经搜索过当前索引 i 的结果。如果在 memo 数组中存在已计算的值,则直接返回该值作为结果,避免重复计算。
1)如果当前索引 i 小于 0,表示没有可选的房屋可偷窃,返回 0。
否则,根据动态规划的思想,选择在当前房屋偷窃或者不偷窃的最大值。2)使用递归调用 dfs 方法,分别计算不偷窃当前房屋的结果(即 dfs(i - 1))和偷窃当前房屋的结果(即 dfs(i - 2) + nums[i])。
3)取两种情况的最大值作为当前索引 i 的结果,并将其存储在 memo 数组中,以备后续使用。
4)返回当前索引 i 的结果作为最终答案。


4).代码示例

  class Solution {private int[] nums, memo;public int rob(int[] nums) {this.nums = nums;this.memo = new int[nums.length];Arrays.fill(memo, -1);return dfs(nums.length - 1);}private int dfs(int i) {//出口if (i < 0) return 0;// 看是否已经搜索过if (memo[i] != -1) {return memo[i];}int result = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);memo[i] = result;return result;}}

5).总结

  • 转移方程怎么写。

试题链接:

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

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

相关文章

神经网络常用激活函数详解

&#x1f380;个人主页&#xff1a; https://zhangxiaoshu.blog.csdn.net &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️&#xff0c;如有错误敬请指正! &#x1f495;未来很长&#xff0c;值得我们全力奔赴更美好的生活&…

科技界年度大戏剧情终结:Open AI宣布ChatGPT创始人奥特曼回归

就在刚刚&#xff0c;在Sam Altman在X平台表示&#xff1a; 我喜欢 Openai&#xff0c;过去几天我所做的一切都是为了让这个团队及其使命保持一致。当我决定在周日晚上加入微软时&#xff0c;很明显这对我和团队来说是最好的道路。在新董事会和 w satya 的支持下&#xff0c;我…

1.Gin 介绍

1.Gin 介绍 介绍 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者&#xff0c;我们推荐你使用 Gin 框架。 Gin 最擅长的就是 Api 接口的高并发&#xff0c;如果项目的规模不大&#xff0c;业务相对简单&a…

Linux:进度条(小程序)以及git三板斧

Linux小程序&#xff1a;进度条 在实现小程序前我们要弄清楚&#xff1a; 1.缓冲区&#xff1b; 2.回车与换行。 缓冲区&#xff1a; 分别用gcc来编译下面两个程序&#xff1a; 程序一&#xff1a; #include <stdio.h> int main() { printf("hello Makefil…

飞瓜数据B站丨B站UP主11月第3周榜单排行榜榜单(B站平台)发布!

飞瓜轻数发布2023年11月13日-11月19日飞瓜数据UP主排行榜&#xff08;B站平台&#xff09;&#xff0c;通过充电数、涨粉数、成长指数、带货数据等维度来体现UP主账号成长的情况&#xff0c;为用户提供B站号综合价值的数据参考&#xff0c;根据UP主成长情况用户能够快速找到运营…

云备份——初步认识及环境搭建

文章目录 整体功能简介云备份功能实现目标服务器程序负责功能细分服务端模块划分客户端功能细分客户端模块划分 环境搭建gcc安装 jsoncppbundle库 与 httplib库安装 整体功能简介 云备份功能 自动将本地计算机上指定文件夹中需要备份的文件上传备份到服务器中 并且能够通过浏…

基于Apache部署虚拟主机网站

文章目录 Apache释义Apache配置关闭防火墙和selinux 更改默认页内容更改默认页存放位置个人用户主页功能基于口令登录网站虚拟主机功能基于ip地址相同ip不同域名相同ip不同端口 学习本章完成目标 1.httpd服务程序的基本部署。 2.个人用户主页功能和口令加密认证方式的实现。 3.…

Spring框架学习 -- 核心思想

目录 (1) Spring是什么? (2) 什么是IOC容器? (3) 从传统开发认识spring (4) 这种传统开发的缺陷 (5)解决传统开发中的缺陷 (6) 对比总结规律 (7) 理解IOC 创作不易多多支持 (1) Spring是什么? 我们常说的Spring的全称是: Spring Framework(Spring框架), 它是一个开源…

【广州华锐互动】VR防溺水安全内容体验提高群众防溺水意识

在全球各地&#xff0c;溺水是导致儿童和青少年死亡的主要原因之一。据世界卫生组织的统计&#xff0c;全球每年有超过36万人因溺水而死亡&#xff0c;其中大部分是儿童和青少年。因此&#xff0c;提供有效的防溺水教育和培训至关重要。随着科技的发展&#xff0c;虚拟现实&…

CF 1894A 学习笔记 思维 题意理解分析

原题 A. Secret Sport time limit per test 3 seconds memory limit per test 512 megabytes input standard input output standard output Lets consider a game in which two players, A and B, participate. This game is characterized by two positive integer…

MyBatis Generator 插件 详解自动生成代码

MyBatis Generator&#xff08;MBG&#xff09;是MyBatis和iBATIS的代码生成器。可以生成简单CRUD操作的XML配置文件、Mapper文件(DAO接口)、实体类。实际开发中能够有效减少程序员的工作量&#xff0c;甚至不用程序员手动写sql。 它将为所有版本的MyBatis以及版本2.2.0之后的i…

【Java基础】Java导Excel攻略

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

【JavaEE】操作系统与进程

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《JavaEE》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&…

京东小程序:无代码开发实现API集成,连接电商平台、CRM和客服系统

无需复杂API开发&#xff0c;京东小程序连接电商平台 京东小程序平台以其全开放的生态模式&#xff0c;让商家享有京东系APP流量福利、海量SKU和开放能力&#xff0c;提升用户体验&#xff0c;同时也带来了新商机。京东小程序的最大优势在于&#xff0c;商家无需进行复杂的API…

驶入产业发展快车道,汉鑫科技人工智能研发中心正式启用!

11月18日&#xff0c;汉鑫科技人工智能研发中心正式启用。中心立足烟台&#xff0c;服务全国&#xff0c;聚焦工业智能、智能网联、智慧城市三大业务板块&#xff0c;以人工智能技术赋能政企实现“数智化”转型升级。该中心的启用标志着汉鑫科技在人工智能研发应用领域迈上了新…

二百零四、Flume——登录监听窗口报错Ncat: bind to :::44444: Address already in use. QUITTING.

一、目的 Flume安装好后测试开启监听窗口44444&#xff0c;结果报错Ncat: bind to :::44444: Address already in use. QUITTING. 二、报错详情 Ncat: bind to :::44444: Address already in use. QUITTING. 三、报错原因 经过分析发现&#xff0c;44444窗口已经被占用 […

el-input限制输入整数等分析

文章目录 前言1、在 Vue 中&#xff0c;可以使用以下几种方式来限制 el-input 只能输入整数1.1 设置input 的 type为number1.2 使用inputmode1.3 使用自定义指令1.4 使用计算属性1.5 使用 onafterpaste ,onkeyup1.6 el-input-number 的precision属性 总结 前言 input 限制输入…

前端学习--React(1)

一、React简介 React由Meta公司研发&#xff0c;是一个用于 构建Web和原生交互界面的库 优势&#xff1a;组件化开发、不错的性能、丰富生态&#xff08;所有框架中最好&#xff09;、跨平台&#xff08;web、ios、安卓&#xff09; 开发环境搭建 打开相应文件夹 新建终端并…

【深度学习实验】注意力机制(四):点积注意力与缩放点积注意力之比较

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、实验内容0. 理论介绍a. 认知神经学中的注意力b. 注意力机制 1. 注意力权重矩阵可视化&#xff08;矩阵热图&#xff09;2. 掩码Softmax 操作3. 打分函数——加性注意力模型3. 打分函数——点积注意力与缩放…