当前位置: 首页 > news >正文

递归学习——记忆化搜索

目录

​编辑

一,概念和效果

二,题目

1.斐波那契数

1.题目

2.题目接口

3.解题思路

2.不同的路径

1.题目

2.题目接口

3.解题思路

3.最长增长子序列

1.题目

2.题目接口

3.解题思路

4.猜数字游戏II

1.题目

2.题目接口

3.解题思路

总结:


一,概念和效果

记忆化搜索可以说是带备忘录的递归实现这个算法的目的便是减少递归时对同一个节点的多次遍历从而提高学习效率。学习这个算法,理解这个算法最好的方式便是通过能够用记忆化搜索的题目来理解。

二,题目

1.斐波那契数

1.题目

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

2.题目接口

class Solution {
public:int fib(int n) {}
};

3.解题思路

相信大家都知道如何解决斐波那契数的问题。这个问题的经典解决方式便是运用到递归解法。使用递归时要明确的便是递归的出口。斐波那契数的递归出口便是在n == 0或者n==1时。这两个条件下的返回值便是它们本身。当n不等于0和1时f(n) = f(n-1)+f(n-2)条件成立。

根据以上思路便可以写出如下解题代码:

class Solution {
public:int fib(int n) {return dfs(n);}int dfs(int n){if(n == 0||n == 1){return n;}return dfs(n-1)+dfs(n-2);}
};

但是我们都知道在递归时会有大量的重复计算。比如当n == 5时递归展开图如下:

在这里可以看到2这个节点被求了很多次,这样子便是很大的浪费了。这个时候为了提高效率便可以采用记忆化搜索的方式。记忆化搜索的实现其实也非常的简单,也就是当我们得到一个结果时便将其记录下来。当我们想要再次遍历相同的节点时只要看前面是否有记录过,若记录过便不再访问直接返回之前记录过的结果就行了。比如斐波那契数列这道题的记忆化搜索方式的解题代码如下:

class Solution {
public:vector<int>memo;//表示备忘录int fib(int n) {memo = vector<int>(n+1);//初始化return dfs(n);}int dfs(int n){if(n == 0||n == 1){return n;}if(memo[n]!=0)//册中已求便无需再求{return memo[n];}memo[n] = dfs(n-1)+dfs(n-2);//记录在册return memo[n];}
};

2.不同的路径

1.题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

2.题目接口

class Solution {
public:int uniquePaths(int m, int n) {}
};

3.解题思路

因为机器人只能向前或者向下走,所以要到达finish位置的话首先就要到达finish的上面和左边这两个位置:

要到达这两个位置的话便又要到达这两个位置的上面和下面位置。以次类推得到公式:

f(finishi,finishj) = f(finishi-1,finishj)+f(finishi,finishj-1)。得到这个关系我们便可以知道这道题和斐波那契数列有的一拼,所以自然就会想到递归的解法。在这里便要寻找递归条件了。

1.因为目中给的m与n表示的是网格的长与宽。所以当m == 1&&n == 1时就意味着网格里面只有一个格子,也就是机器人就在右下角的格子了所以返回1。

2.当给的m与n中有一个为0的话,也就是网格的长或者宽为0,也就表示没有格子于是返回0。

根据以上分析写出代码如下:

class Solution {
public:int uniquePaths(int m, int n) {return dfs(m,n);} int dfs(int m,int n){if(m == 1&&n==1){return 1;}if(m ==0||n==0){return 0;}return dfs(m-1,n)+dfs(m,n-1);}
};

但是这个代码会超时,所以我们得优化这个代码让这个代码变得更快。优化的方式便是记忆化搜索:

class Solution {
public:vector<vector<int>>memo;int uniquePaths(int m, int n) {memo = vector<vector<int>>(m+1,vector<int>(n+1));return dfs(m,n);} int dfs(int m,int n){if(memo[m][n]!=0){return memo[m][n];}if(m == 1&&n==1){return 1;}if(m ==0||n==0){return 0;}memo[m][n] = dfs(m-1,n)+dfs(m,n-1);return  memo[m][n];}
};

可以看到这道题的记忆化搜索处理方式和上一道题一毛一样。

3.最长增长子序列

1.题目

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

2.题目接口

class Solution {
public:int lengthOfLIS(vector<int>& nums) {}
};

3.解题思路

这道题的解题思路其实也不太难,就是要遍历一下每一个下标然后求出以每一个下标的起点为开始位置的子序列长度。但是因为我们要求的是最大长度所以需要比较更新最大长度。以这个思路写成代码如下:

class Solution {
public:int len; int lengthOfLIS(vector<int>& nums) {len = nums.size();int ret = 0;for(int i = 0;i<len;i++){ret = max(ret,dfs(i,nums));//得到以某个下标为起点的最大长度} return ret;}int dfs(int i,vector<int>&nums){int ret = 1;//每一个子序列的最小长度为1for(int x =i+1;x<len;x++ ){if(nums[x]>nums[i]){ret = max(ret,dfs(x,nums)+1);//求出以每一个下标为起点的子序列长度,并每次都更新一下}}return ret;//返回最大值}
};

但是以上代码是通不过的,因为时间限制:

那该怎么办呢?其实很简单,还是和前两道题一样要采用一个记忆化搜索的策略:

class Solution {
public:int len; vector<int>memo;int lengthOfLIS(vector<int>& nums) {len = nums.size();memo = vector<int>(len,1);int ret = 0;for(int i = 0;i<len;i++){ret = max(ret,dfs(i,nums));} return ret;}int dfs(int i,vector<int>&nums){if(memo[i]!=1)//判断一下{return memo[i];}int ret = 1;for(int x =i+1;x<len;x++ ){if(nums[x]>nums[i]){ret = max(ret,dfs(x,nums)+1);}}memo[i] = ret;//记录一下return ret;}
};

然后便过掉了:

4.猜数字游戏II

1.题目

我们正在玩一个猜数游戏,游戏规则如下:

  1. 我从 1 到 n 之间选择一个数字。
  2. 你来猜我选了哪个数字。
  3. 如果你猜到正确的数字,就会 赢得游戏 。
  4. 如果你猜错了,那么我会告诉你,我选的数字比你的 更大或者更小 ,并且你需要继续猜数。
  5. 每当你猜了数字 x 并且猜错了的时候,你需要支付金额为 x 的现金。如果你花光了钱,就会 输掉游戏 。

给你一个特定的数字 n ,返回能够 确保你获胜 的最小现金数,不管我选择那个数字 。

2.题目接口

class Solution {
public:int getMoneyAmount(int n) {}
};

3.解题思路

这道题该咋做呢?或者说这道题是什么意思呢?以输入一个数字10为例吧。我们要猜数字时便要在[1,10]之间猜测。于是我们猜数字策略便有很多种。比如一下几种:

1.当开始位置为1时

这里的至少要1+2+3+4+5+6+7+8块钱。

2.当我们一开始便选到5时:

还有一种便是这道题目给的最优解法:

在这个最优解法里边我们要做的便是找到这里的最大钱数也就是7+9 = 16。所以我们要做的便暴力搜索找出这个最优策略里的最大钱数。怎么做呢?其实还是遍历,抽象成下图:

这里一个一个试验的i便是为了得到最优模型而设计的。返回最大值便是为了得到每一个模型里面的最坏情况然后让每一个情况比较一下得到最优模型的最坏情况。写成代码如下:

class Solution {
public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(left>=right)//当数组范围中只有一个数字或者范围不合法时便返回0。{return 0;}int ret = INT_MAX;//记录最优模型的最坏情况。for(int head = left;head<right;head++){int l = dfs(left,head-1)+head;//左结果int r = dfs(head+1,right)+head;//右结果ret = min(ret,max(l,r));//最优模型下的追怀情况}return ret;}
};

这样便得到了代码了,这个代码是对的但是遗憾的是这个代码过不了:

接下来采用记忆化搜索方式:

class Solution {
public:vector<vector<int>>memo;int getMoneyAmount(int n) {memo = vector<vector<int>>(n+1,vector<int>(n+1));return dfs(1,n);}int dfs(int left,int right){if(memo[left][right]!=0){return memo[left][right];}if(left>=right){return 0;}int ret = INT_MAX;for(int head = left;head<right;head++){int l = dfs(left,head-1)+head;int r = dfs(head+1,right)+head;ret = min(ret,max(l,r));}memo[left][right] = ret;return ret;}
};

这样便可以过掉了:

总结:

其实记忆化搜索的目的便是实现剪枝操作,提高递归效率。当我们的递归操作里有大量的重复的递归操作时便可以用记忆化搜索的方式来提高递归效率。

相关文章:

递归学习——记忆化搜索

目录 ​编辑 一&#xff0c;概念和效果 二&#xff0c;题目 1.斐波那契数 1.题目 2.题目接口 3.解题思路 2.不同的路径 1.题目 2.题目接口 3.解题思路 3.最长增长子序列 1.题目 2.题目接口 3.解题思路 4.猜数字游戏II 1.题目 2.题目接口 3.解题思路 总结&a…...

ChatGPT帮助一名儿童确诊病因,之前17位医生无法确诊

9月13日&#xff0c;Today消息&#xff0c;一位名叫Alex的4岁儿童得了一种浑身疼痛的怪病&#xff0c;每天需要服用Motrin&#xff08;美林&#xff09;才能止痛。3年的时间&#xff0c;看了17名医生无法确诊病因。&#xff08;新闻地址&#xff1a;https://www.today.com/heal…...

Laf 云开发平台及其实现原理

Laf 产品介绍 自我介绍 大家好&#xff0c;我是来自 Laf 团队的王子俊&#xff0c;很高兴今天能在这里给大家分享我们 Laf 云开发平台及其实现原理。本来想说一点什么天气之类的话作为开头&#xff0c;但主持人都说完啦&#xff0c;我就不多说了&#xff0c;还是直接开始今天…...

浅谈STL|STL函数对象篇

一.函数对象概念 概念: 重载函数调用操作符的类&#xff0c;其对象常称为函数对象 函数对象使用重载的()时&#xff0c;行为类似函数调用&#xff0c;也叫仿函数 本质: 函数对象(仿函数)是一个类&#xff0c;不是一个函数 特点 函数对象在使用时&#xff0c;可以像普通函数那…...

自建私人图床方案:使用Cpolar+树洞外链轻松部署超轻量级图床,实现高效图片存储

文章目录 1.前言2. 树洞外链网站搭建2.1. 树洞外链下载和安装2.2 树洞外链网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar临时数据隧道3.2 Cpolar稳定隧道&#xff08;云端设置&#xff09;3.3 Cpolar稳定隧道&#xff08;本地设置&#xff09; 4.公网访问测试5.结语…...

从零基础到精通Flutter开发:一步步打造跨平台应用

&#x1f482; 个人网站:【工具大全】【游戏大全】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 寻找学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 导言 Flutter是一种流行…...

SpringBoot整合WebSocket【代码】

系列文章目录 一、SpringBoot连接MySQL数据库实例【tk.mybatis连接mysql数据库】 二、SpringBoot连接Redis与Redisson【代码】 三、SpringBoot整合WebSocket【代码】 四、SpringBoot整合ElasticEearch【代码示例】 文章目录 系列文章目录代码下载地址一、效果演示二、引入依赖…...

微服务 第一章 Java线程池技术应用

系列文章目录 第一章 Java线程池技术应用 文章目录 系列文章目录[TOC](文章目录) 前言1、Java创建线程方式回顾1.1、继承Thread类(只运行一次)1.1.1、改造成主线程常驻&#xff0c;每秒开启新线程运行1.1.2、匿名内部类1.1.3、缺点1.1.4、扩展知识&#xff1a;Java内部类1.1.4…...

行业追踪,2023-09-14

自动复盘 2023-09-14 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…...

传输层协议--UDP

引入 传输层负责数据能够从发送端传输到接收端。 端口号&#xff08;Port&#xff09; 端口号标识了一个主机上进行通信的一个进程。 两个问题&#xff1a; 1. 一个进程可以绑定多个端口号吗&#xff1f;--可以 2.一个端口号可以绑定多个进程吗&#xff1f;--不可以 我们…...

微信会员卡开发流程

功能需求&#xff1a; 通过微信第三方平台创建的模板小程序&#xff0c;想要实现用户在小程序支付一定金额后领取会员卡&#xff0c;领取会员卡后可给用户下发一定数量的优惠券&#xff0c;并且实现用户在小程序消费享受商品折扣。 开发流程&#xff1a; 一、了解微信的3个平…...

《算法竞赛·快冲300题》每日一题:“点灯游戏”

《算法竞赛快冲300题》将于2024年出版&#xff0c;是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码&#xff0c;以中低档题为主&#xff0c;适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 点…...

常见高级语言的输入与输出训练(一)

文章目录 题目概述1 输入描述: 输出描述: 输入 输出 示例C语言代码 题目概述2 题目描述 输入描述: 输出描述: 输入 输出 示例Java代码 前言 本文主要讲解两个算法题的代码实现 题目概述1 计算ab 打开以下链接可以查看正确的代码 数据范围&#xff1a;数据组数满…...

恭喜!龙蜥获得 2023 大学生操作系统设计赛二等奖及特殊贡献奖

经过多月的激烈角逐&#xff0c;2023 全国大学生系统能力大赛操作系统设计赛&#xff08;以下简称“2023 大学生操作系统赛”&#xff09; 圆满结束。经过 2023 大学生操作系统赛评审组和技术委员会的复核&#xff0c;面向全国公布了此次大赛的获奖名单。龙蜥社区不负众望&…...

中项系统集成项目管理2023上半年真题及解析

中项系统集成项目管理2023上半年真题及解析 上午题1. 在 (1) 领域&#xff0c;我国还远未达到世界先进水平&#xff0c;需要发挥新型举国体制优势&#xff0c;集中政府和市场两方面的力量全力发展2. ChatGPT于 2022年 11 月 30 日发布&#xff0c;它是人工智能驱动的 (2) 工具3…...

实时显示当前文件夹下的文件大小,shell脚本实现

图片来源于网络&#xff0c;如果侵权请联系博主删除&#xff01; 需求&#xff1a; 写一个shell终端命令&#xff0c;实时显示当前文件夹下的文件大小 实现&#xff1a; 您可以使用以下的Shell脚本命令来实时显示当前文件夹下的文件大小&#xff1a; while true; docleardu …...

7、Spring之依赖注入源码解析(下)

resolveDependency()实现 该方法表示,传入一个依赖描述(DependencyDescriptor),该方法会根据该依赖描述从BeanFactory中找出对应的唯一的一个Bean对象。 @Nullable Object resolveDependency(DependencyDescriptor descriptor, @Nullable String requestingBeanName,@Null…...

图片码二次渲染绕过

目录 一、环境 1、代码 2、文件处理方式 3、图片码的制作 二、绕过图片重构 1、可行性分析 2、数据比对 3、完成绕过 一、环境 以upload-labs靶场第十七关为例 1、代码 源码为&#xff1a; <?php include ../config.php; include ../head.php; include ../menu.…...

点评项目核心内容

目录 拦截器设置 集群的session共享问题 基于redis实现共享session登录 创建bean对象技巧 什么是缓存 使用缓存来处理对象 使用String类型缓存来处理集合 缓存更新策略 主动更新策略 缓存穿透 空串""和null的区别 缓存null值解决穿透问题 缓存雪崩 缓存击穿…...

海外商城小程序为什么这么受欢迎?

随着全球化的进程海外商城小程序在近年来获得了广泛的关注和使用。海外商城小程序是一种基于互联网技术的应用程序&#xff0c;为用户提供了便捷的购物体验和跨境交易服务。本文将深入探讨海外商城小程序的受欢迎原因&#xff0c;从多个维度进行分析就其未来发展进行思考&#…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...

k8s从入门到放弃之Pod的容器探针检测

k8s从入门到放弃之Pod的容器探针检测 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;容器探测是指kubelet对容器执行定期诊断的过程&#xff0c;以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...

spring boot使用HttpServletResponse实现sse后端流式输出消息

1.以前只是看过SSE的相关文章&#xff0c;没有具体实践&#xff0c;这次接入AI大模型使用到了流式输出&#xff0c;涉及到给前端流式返回&#xff0c;所以记录一下。 2.resp要设置为text/event-stream resp.setContentType("text/event-stream"); resp.setCharacter…...