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

记忆化搜索（5题）

news 来源：原创 2025/5/21 17:49:56

是什么？是一个带备忘录的递归

如何实现记忆化搜索

1.添加一个备忘录（建立一个可变参数和返回值的映射关系）

2.递归每次返回的时候把结果放到备忘录里

3.在每次进入递归的时候往备忘录里面看看。

1.斐波那契数列

2.不同路径

3.最长递增子序列

4.猜数字大小2

5.矩阵中最长的递增路径

1.斐波那契数列

LCR 126. 斐波那契数 - 力扣（LeetCode）

我们再看看动态规划的做法。我们发现其实两者具有一一对应的关系，只不过一种是用递归形式呈现，另一种是用递推形式呈现

小问题：

1. 所有的递归（暴搜、深搜），都能改成记忆化搜索吗？

不是的，只有在递归的过程中，出现了大量完全相同的问题时，才能用记忆化搜索的方式优化

2.带备忘录的递归vs动态规划 vs记忆化搜索

本质上是一回事

3.自顶向下 vs 自低向上

不同的看待问题的方式

4.暴搜->记忆化搜索->动态规划

可以为我们的动态规划提供一个方向

我们创建一个备忘录的时候需要在里面填入一个不可能取到的值，以此来判断备忘录是否已经更新

class Solution {
public:int memo[110];//一个备忘录int fib(int n) {memset(memo, -1, sizeof(memo));return dfs(n);}int dfs(int n){if(memo[n] != -1)return memo[n];//每次进入的时候查看备忘录里面是否存值if(n == 1){memo[1] = 1;return memo[1];//返回之前把值存到备忘录里面}else if(n == 0){memo[0] = 0;return memo[0];}else {memo[n] = (dfs(n-1) + dfs(n - 2))%1000000007;return memo[n];}}
};

2.不同路径

62. 不同路径 - 力扣（LeetCode）

1.暴力搜索（会超时）

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

2.记忆化搜索

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

3.最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

1.暴搜（会超时）

dfs（pos）的任务是返回以nums[pos]为开头的最长子序列

我们在主函数里面从头开始遍历一次，找到最大的那个，ret 一开始为0.

在dfs函数中，ret一开始为1，因为已经进入dfs函数的情况下最少也有一个数。

我们从pos的下一位开始，遍历到结尾，每遍历到一个位置我们判断这个值是否比nums【i】大，如果更大说明它可以连接到nums【i】后面，我们再更新ret， ret = max(ret, dfs(nums, i) + 1);

class Solution {
public:int n;int lengthOfLIS(vector<int>& nums) {int ret = 0;n = nums.size();for(int i = 0; i < n; i++){ret = max(dfs(nums, i), ret);}return ret;}int dfs(vector<int>& nums, int pos){int ret = 1;for(int i = pos + 1; i < n; i++){if(nums[i] > nums[pos]){ret = max(ret, dfs(nums, i) + 1);}}return ret;}
};

2.记忆化搜索

记录数据需要在返回之前记录。

class Solution {
public:int n;int lengthOfLIS(vector<int>& nums) {int ret = 0;n = nums.size();vector<int> memo(n);for(int i = 0; i < n; i++){ret = max(dfs(nums, i,memo), ret);}return ret;}int dfs(vector<int>& nums, int pos,vector<int>& memo){if(memo[pos] != 0)return memo[pos];int ret = 1;for(int i = pos + 1; i < n; i++){if(nums[i] > nums[pos]){ret = max(ret, dfs(nums, i, memo) + 1);}}memo[pos] = ret;return ret;}
};

3.递归代码

dp[i]表示的是从i下标开始最大的一个子序列。

因此我们从末尾开始填dp表，每个位置最小的子序列是自身，因此dp表每个位置先赋值为1.

每次进行比较之后才更新

if(nums[i] < nums[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}

最后的结果从dp表里面挑一个最大的即可。

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

4.猜数字大小2

375. 猜数字大小 II - 力扣（LeetCode）

1.暴搜（会超时）

这题让我们求不管猜的是哪个数字确保获胜的最小金额

首先，猜的策略有很多种，我们用暴力搜索，从小到大依次以某个值为根，然后分出两个树，继续对两个树进行相同的操作。

我们要确保无论它让我们猜哪个值都要获胜，那么就应该找每棵树里面花钱最多的策略，

我们使得int l = dfs(left,i - 1);
int r = dfs(i + 1, right);

花钱最多的即根节点+ 左右两树中花钱多的即 i + max(l, r) ，

同时又要最少金额，那么就从各种一定会获胜的金额中取出最小的即可

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

2.记忆化搜索

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

5.矩阵中最长的递增路径

LCR 112. 矩阵中的最长递增路径 - 力扣（LeetCode）

class Solution {
public://int check[210][210];int m,n;int dx[4] = {0 , -1, 0, 1};int dy[4] = {-1, 0, 1, 0};int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size();n = matrix[0].size();vector<vector<int>> memo(m, vector<int>(n, -1));int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){ret = max(ret,dfs(i,j,matrix,memo));}}return ret;}int dfs(int x, int y, vector<vector<int>>& matrix, vector<vector<int>>& memo){if(memo[x][y] != -1)return memo[x][y];int ret = 1;for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >= 0 && j < n ){if(matrix[i][j] > matrix[x][y]){ret = max(ret, dfs(i,j,matrix,memo) + 1);}}}memo[x][y] = ret;return ret;}
};

记忆化搜索（5题）

是什么？ 是一个带备忘录的递归如何实现记忆化搜索 1.添加一个备忘录（建立一个可变参数和返回值的映射关系） 2.递归每次返回的时候把结果放到备忘录里 3.在每次进入递归的时候往备忘录里面看看。目录 1.斐波那契数列 2.不同路径 3.最…...

编程日记 2025/5/21 17:49:56

强化学习笔记——4策略迭代、值迭代、TD算法

基于策略迭代的贝尔曼方程和基于值迭代的贝尔曼方程，关系还是不太理解首先梳理一下： 通过贝尔曼方程将强化学习转化为值迭代和策略迭代两种问题求解上述两种贝尔曼方程有三种方法：DP（有模型），MC&#xff…...

编程日记 2025/5/21 17:19:32

nginx目录结构和配置文件

nginx目录结构 [rootlocalhost ~]# tree /usr/local/nginx /usr/local/nginx ├── client_body_temp # POST 大文件暂存目录 ├── conf # Nginx所有配置文件的目录 │ ├── fastcgi.conf # fastcgi相关参…...

编程日记 2025/5/21 17:36:41

Spring RESTful API 设计与实现

Spring RESTful API的设计与实现极大地提升了开发效率和系统可维护性，通过遵循RESTful设计原则，使得API结构清晰、行为一致，便于扩展和维护。它在构建微服务架构中扮演着核心角色，支持松耦合的通信，同时通过标准的HTTP协议和数据格式增强了系统的互操作性。结合Spring Sec…...

编程日记 2025/5/21 4:45:12

【玩转全栈】--创建一个自己的vue项目

目录 vue介绍创建vue项目 vue页面介绍 element-plus组件库启动项目 vue介绍 Vue.js 是一款轻量级、易于上手的前端 JavaScript 框架，旨在简化用户界面的开发。它采用了响应式数据绑定和组件化的设计理念，使得开发者可以通过声明式的方式轻松管理数据和…...

编程日记 2025/5/21 17:07:58

【Envi遥感图像处理】008：波段（批量）分离与波段合成

文章目录一、波段分离提取1. 提取单个波段2. 批量提取单个波段二、波段合成相关阅读：【ArcGIS微课1000例】0058：波段合成(CompositeBands)工具的使用一、波段分离提取 1. 提取单个波段...

编程日记 2025/5/19 23:39:36

数据结构-Stack和栈

1.栈 1.1什么是栈栈是一种特殊的线性表，只允许在固定的一段进行插入和删除操作，进行插入和删除操作的一段称为栈顶，另一端称为栈底。栈中的数据元素遵顼后进先出LIFO（Last In First Out）的原则，就像一…...

编程日记 2025/5/17 4:02:04

内容检索（2025.01.30）

随着创作数量的增加，博客文章所涉及的内容越来越庞杂，为了更为方便地阅读，后续更新发布的文章将陆续在此汇总并附上原文链接，感兴趣的小伙伴们可持续关注文章发布动态！ 博客域名：http://my-signal.blog.cs…...

编程日记 2025/5/21 17:44:42

牛客周赛 Round 77

题目目录 C-小红走网格解题思路参考代码 D-隐匿社交网络解题思路参考代码 F-计树解题思路参考代码 C-小红走网格解题思路根据裴蜀定理：设a，b是不全为0的整数，对任意整数x，y，满足gcd（a，b&…...

编程日记 2025/5/19 22:58:08

c++面试：类定义为什么可以放到头文件中

这个问题是刚了解预编译的时候产生的疑惑。声明是指向编译器告知某个变量、函数或类的存在及其类型，但并不分配实际的存储空间。声明的主要目的是让编译器知道如何解析程序中的符号引用。定义不仅告诉编译器实体的存在，还会为该实体分配存储空间&#…...

编程日记 2025/5/20 13:21:47

Oracle查看数据库表空间使用情况

Oracle RAC环境查看表空间使用情况查询字段释义： NEED_ADDFILE,--是否需增加表空间文件 TABLESPACE_NAME,--表空间名称 TABLESPACE_FILE_COUNT, --表空间当前数据文件数量 NOW_FILEENABLE_BLOCKS,--表空间文件当前数据块数 NOW_FILEENABLE_BYTES_GB,--表空间文件当…...

编程日记 2025/5/20 23:03:00

Spring Boot 热部署实现指南

在开发 Spring Bot 项目时，热部署功能能够显著提升开发效率，让开发者无需频繁重启服务器就能看到代码修改后的效果。下面为大家详细介绍一种实现 Spring Boot 热部署的方法，同时也欢迎大家补充其他实现形式。步骤一、开启 IDEA 自动编译功能…...

编程日记 2025/5/19 10:12:10

如何构建ObjC语言编译环境?构建无比简洁的clang编译ObjC环境？Windows搭建Swift语言编译环境？

如何构建ObjC语言编译环境? 除了在线ObjC编译器，本地环境Windows/Mac/Linux均可以搭建ObjC编译环境。 Mac自然不用多说，ObjC是亲儿子。(WSL Ubuntu 22.04) Ubuntu可以安装gobjc/gnustep和gnustep-devel构建编译环境。 sudo apt-get install gobjc gnus…...

编程日记 2025/5/20 9:18:44

C++——类和对象（下）

1.初始化列表之前我们实现构造函数时，初始化成员变量主要使用函数体内赋值，构造函数初始化还有一种方式，就是初始化列表，初始化列表的使用方式是以一个冒号开始，接着是一个以逗号分隔的数据成员列表，每个…...

编程日记 2025/5/21 13:59:32

R 字符串：深入理解与高效应用

R 字符串：深入理解与高效应用引言在R语言中，字符串是数据处理和编程中不可或缺的一部分。无论是数据清洗、数据转换还是数据分析，字符串的处理都是基础技能。本文将深入探讨R语言中的字符串概念，包括其基本操作、常见函数以及高效应用方法。字符串基本概念字符串定…...

编程日记 2025/5/17 4:02:08

C#面试常考随笔7:什么是匿名⽅法？还有Lambda表达式？

匿名方法本质上是一种没有显式名称的方法，它可以作为参数传递给需要委托类型的方法，常用于事件处理、回调函数等场景，能够让代码更加简洁和紧凑。使用场景事件处理：在处理事件时，不需要为每个事件处理程序单独定义…...

编程日记 2025/5/21 17:21:05

舵机型号与识别

舵机型号繁多，不同品牌和制造商有不同的命名规则。常见的舵机品牌包括 Futaba、Hitec、Tower Pro、Savox、JX Servo 等。以下是舵机型号的常见识别方法以及一些典型的型号示例： 一、舵机型号的识别方法型号命名规则： 舵机型号通常由字母和数…...

编程日记 2025/5/21 16:49:40

【memgpt】letta 课程6：多agent编排

Lab 6: Multi-Agent Orchestration 多代理协作 letta 是作为一个服务存在的，app通过restful api 通信多智能体之间如何协调与沟通？相互发送消息共享内存块，让代理同步到不同的服务的内存块...

编程日记 2025/5/21 16:53:19

《DeepSeek手机版：开启AI移动新时代》

DeepSeek 手机版爆火：现象与背景在当今数字化时代，AI 技术的发展日新月异，如同一股汹涌澎湃的浪潮，深刻地改变着我们的生活。而在这股浪潮中，DeepSeek 手机版宛如一颗璀璨的新星，迅速崛起，引发…...

编程日记 2025/5/21 4:01:05

列表（列表是什么）

你将学习列表是什么以及如何使用列表元素。列表让你能够在一个地方存储成组的信息，其中可以只包含几个元素，也可以包含数百万个元素。列表是新手可直接使用的最强大的Python功能之一，它融合了众多重要的编程概念。列表是什么列表由一系列…...

编程日记 2025/5/21 17:16:37

C语言-运算符

1. 按位与运算符（&） 按位与运算符对两个整数的每一位执行“与”操作。只有当两个相应位都为 1 时，结果才为 1 ；否则为 0。 // 示例 int a 5; // 二进制: 0101 int b 3; // 二进制: 0011 int result a & b; …...

编程日记 2025/5/20 17:29:55

yolov11、yolov8部署的7种方法（yolov11、yolov8部署rknn的7种方法），一天一种部署方法，7天入门部署

由于涉及量化、部署两个领域，本博文难免有不对之处，欢迎指正。本博客对 yolov11（yolov8）尝试了7种不同的部署方法，在最基础的模型上一步一步的去掉解码相关的操作（移到后处理种进行）&#xff0…...

编程日记 2025/5/21 17:25:34

事务03之MVCC机制

MVCC 多版本并发控制机制文章目录 MVCC 多版本并发控制机制一：并发事务的场景1：读读场景2：写写场景3：读写 or 写读场景二：MVCC机制综述1：MVCC日常生活的体现2：多版本并发控制三：M…...

编程日记 2025/5/21 10:16:23

Autosar-Os是怎么运行的？（时间保护）

写在前面： 入行一段时间了，基于个人理解整理一些东西，如有错误，欢迎各位大佬评论区指正！！！ 1.功能概述 AUTOSAR OS 的四大可定制类型凸显了时间保护（Timing Protection）…...

编程日记 2025/5/19 22:59:12

论文阅读(九)：通过概率图模型建立连锁不平衡模型和进行关联研究：最新进展访问之旅

1.论文链接：Modeling Linkage Disequilibrium and Performing Association Studies through Probabilistic Graphical Models: a Visiting Tour of Recent Advances 摘要： 本章对概率图模型（PGMs）的最新进展进行了深入的回顾&…...

编程日记 2025/5/18 8:31:35

python学opencv|读取图像（五十二）使用cv.matchTemplate()函数实现最佳图像匹配

【1】引言前序学习了图像的常规读取和基本按位操作技巧，相关文章包括且不限于： python学opencv|读取图像-CSDN博客 python学opencv|读取图像（四十九）原理探究：使用cv2.bitwise()系列函数实现图像按位运算-CSDN博客…...

编程日记 2025/5/21 3:07:48

视频脚本生成器（基于openai API和streamlit）

utils.py： # 所有和ai交互的代码放进utils.py里（utils 通常是 “utilities” 的缩写，意为 “实用工具” 或 “实用函数”）from langchain.prompts import ChatPromptTemplate from langchain_openai import ChatOpenAI from lan…...

编程日记 2025/5/21 10:49:05

《LLM大语言模型+RAG实战+Langchain+ChatGLM-4+Transformer》

文章目录 Langchain的定义Langchain的组成三个核心组件实现整个核心组成部分为什么要使用LangchainLangchain的底层原理Langchain实战操作LangSmithLangChain调用LLM安装openAI库-国内镜像源代码运行结果小结使用Langchain的提示模板部署Langchain程序安装langserve代码请求格…...

编程日记 2025/5/21 17:38:35

【MySQL — 数据库增删改查操作】深入解析MySQL的 Update 和 Delete 操作

1. 测试数据 mysql> select* from exam1; ----------------------------------------- | id | name | Chinese | Math | English | ----------------------------------------- | 1 | 唐三藏 | 67.0 | 98.0 | 56.0 | | 2 | 孙悟空 | 87.0 | 78.…...

编程日记 2025/5/16 2:43:06

AnyThingLLM本地私有知识库搭建

***************************************************** 环境准备操作系统：Windows11 内存：32GB RAM 存储：预留 300GB 可用空间显存: 16G 网络: 100M带宽前置准备: 已安装ollama环境 deepseek本地大模型 ***************************…...

编程日记 2025/5/19 17:06:05

数仓ETL测试

提取，转换和加载有助于组织使数据在不同的数据系统中可访问，有意义且可用。ETL工具是用于提取，转换和加载数据的软件。在当今数据驱动的世界中，无论大小如何，都会从各种组织，机器和小工具中生成大量数据。 …...

编程日记 2025/5/21 17:47:43

leetcode——将有序数组转化为二叉搜索树（java）

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。示例 1： 输入：nums [-10,-3,0,5,9] 输出：[0,-3,9,-10,null,5] 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答…...

编程日记 2025/5/21 1:27:04

蓝桥杯模拟算法：多项式输出

P1067 [NOIP2009 普及组] 多项式输出 - 洛谷 | 计算机科学教育新生态这道题是一道模拟题，我们需要分情况讨论，我们需要做一下分类讨论 #include <iostream> #include <cstdlib> using namespace std;int main() {int n;cin >> n;for…...

编程日记 2025/5/17 14:31:34

新鲜速递：DeepSeek-R1开源大模型本地部署实战—Ollama + MaxKB 搭建RAG检索增强生成应用

在AI技术快速发展的今天，开源大模型的本地化部署正在成为开发者们的热门实践方向。最火的莫过于吊打OpenAI过亿成本的纯国产DeepSeek开源大模型，就在刚刚，凭一己之力让英伟达大跌18%，纳斯达克大跌3.7%，足足是给中国AI产…...

编程日记 2025/5/18 21:50:14

【张雪峰高考志愿填报】合集

【张雪峰高考志愿填报】合集链接：https://pan.quark.cn/s/89a2d88fa807 高考结束，分数即将揭晓，志愿填报的关键时刻近在眼前！同学们，这可是人生的重要转折点，选对志愿，就像为未来铺就一条…...

编程日记 2025/5/20 0:47:24

【gRPC-gateway】option定义规则及HttpBody响应

HTTP Option 定义规则在 .proto 文件中，通过 google.api.http 注解定义 HTTP 路由规则，控制请求参数映射需要在.proto文件显式 import https://github.com/googleapis/googleapis/tree/master/google/api 一、HTTP Option 定义规则详解 1. 基础路由…...

编程日记 2025/5/19 10:33:42

rsync安装与使用-linux015

使用 rsync 可以非常高效地将文件或目录从一个服务器传输到另一个服务器。能力： 支持 64 位文件、64 位 inode、64 位时间戳、64 位长整型支持套接字对、符号链接、符号链接时间、硬链接、硬链接特殊文件、硬链接符号链接支持 IPv6、访问时间（atimes&…...

编程日记 2025/5/21 14:02:31

一种用于低成本水质监测的软传感器开源方法：以硝酸盐（NO3⁻）浓度为例

论文标题 A Soft Sensor Open-Source Methodology for Inexpensive Monitoring of Water Quality: A Case Study of NO3− Concentrations 作者信息 Antonio Jess Chaves, ITIS Software, University of Mlaga, 29071 Mlaga, Spain Cristian Martn, ITIS Software, Universi…...

编程日记 2025/5/19 12:30:45

剑指 Offer II 011. 0 和 1 个数相同的子数组

comments: true edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20011.%200%20%E5%92%8C%201%20%E4%B8%AA%E6%95%B0%E7%9B%B8%E5%90%8C%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84/README.md 剑指 Offer II 011. 0 和 1 个数相同的子…...

编程日记 2025/5/18 18:10:54

1.斐波那契数列

2.不同路径

3.最长递增子序列

4.猜数字大小2

5.矩阵中最长的递增路径

相关文章：