记忆化搜索

目录

引言:

1. 什么是记忆化搜索?

2. 如何实现记忆化搜索?

一、斐波那契数

1. 题目链接:509. 斐波那契数

2. 题目描述:

3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):

🌴算法思路:

🌴算法代码:

二、不同路径

1. 题目链接:62. 不同路径

2. 题目描述:

3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):

🌴算法思路:

🌴算法代码:

三、最长递增子序列

1. 题目链接:300. 最长递增子序列

2. 题目描述:

3. 解法:

🌴算法思路:

🌴算法代码:

四、猜数字大小 II

1. 题目链接:375. 猜数字大小 II

2. 题目描述:

3. 解法:

🌴算法思路:

🌴算法代码:

五、矩阵中的最长递增路径

1. 题目链接:329. 矩阵中的最长递增路径

2. 题目描述:

3. 解法:

🌴算法思路:

🌴算法代码:


引言:

1. 什么是记忆化搜索?

        记忆化搜索(Memoization Search)是一种通过存储已经遍历过的状态信息,从而避免对同一状态重复遍历的搜索算法。它是动态规划的一种实现方式,特别适用于那些具有重叠子问题最优子结构特性的问题。

        在记忆化搜索中,当算法需要计算某个子问题的结果时,它首先检查是否已经计算过该问题。如果已经计算过,则直接返回已经存储的结果;否则,计算该问题,并将结果存储下来以备将来使用。这种方法可以显著减少重复计算,提高算法的效率。

2. 如何实现记忆化搜索?

实现记忆化搜索的基本步骤通常包括:

  1. 确定问题的动态规划状态和状态转移方程。
  2. 创建一个缓存结构(如数组或哈希表),用于存储子问题的解。
  3. 定义一个递归函数,用于计算问题的解。在递归过程中,首先检查缓存中是否已经有了当前子问题的解,如果有,则直接返回;如果没有,则计算该子问题,并将结果存储到缓存中。
  4. 调用递归函数并返回最终结果。

        记忆化搜索与递推(自底向上的动态规划)的主要区别在于,记忆化搜索是自顶向下的解决问题方法,而递推是自底向上的方法。记忆化搜索适合那些状态转移方程复杂或递归深度不会太深的问题,而递推适合那些状态转移方程简单且递归深度可能过大的问题。


一、斐波那契数

1. 题目链接:509. 斐波那契数

2. 题目描述:

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

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

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

示例 1:

输入:n = 2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2:

输入:n = 3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3:

输入:n = 4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3

提示:

  • 0 <= n <= 30

3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):

🌴算法思路:

暴搜:

  1. 递归含义:给 dfs ⼀个使命,给他⼀个数 n ,返回第 n 个斐波那契数的值;
  2. 函数体:斐波那契数的递推公式;
  3. 递归出口:当 n == 0 或者 n == 1 时,不用套公式。

记忆化搜索:

  1. 加上一个备忘录;
  2. 每次进入递归的时候,去备忘录里面看看;
  3. 每次返回的时候,将结果加入到备忘录里面。

动态规划:

  1. 递归含义 -> 状态表示;
  2. 函数体 -> 状态转移方程;
  3. 递归出口 -> 初始化。

🌴算法代码:

class Solution 
{int memo[31];
public: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 == 0 || n == 1){memo[n] = n;// 记录到备忘录里边return n;}memo[n] = dfs(n - 1) + dfs(n - 2);// 记录到备忘录里边return memo[n];}
};

二、不同路径

1. 题目链接:62. 不同路径

2. 题目描述:

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

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

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

示例 1:

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

3. 解法(暴搜 -> 记忆化搜索 -> 动态规划):

🌴算法思路:

暴搜:

  1. 递归含义:给 dfs ⼀个使命,给他⼀个下标,返回从 [0, 0] 位置走到 [i, j] 位置一共有多少种方法;
  2. 函数体:只要知道到达上面位置的方法数以及到达左边位置的方法数,然后累加起来即可;
  3. 递归出口:当下标越界的时候返回 0 ;当位于起点的时候,返回 1 。

记忆化搜索:

  1. 加上一个备忘录;
  2. 每次进入递归的时候,去备忘录里面看看;
  3. 每次返回的时候,将结果加入到备忘录里面。

动态规划:

  1. 递归含义 -> 状态表示;
  2. 函数体 -> 状态转移方程;
  3. 递归出口 -> 初始化。

🌴算法代码:

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

三、最长递增子序列

1. 题目链接:300. 最长递增子序列

2. 题目描述:

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。

示例 1:

输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4 
解释:最长递增路径为 [1, 2, 6, 9]。

示例 2:

 

输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4 
解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3:

输入:matrix = [[1]]
输出:1

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 231 - 1

3. 解法:

🌴算法思路:

暴搜:

  1. 递归含义:给 dfs ⼀个使命,给他⼀个数 i ,返回以 i 位置为起点的最长递增子序列的长度;
  2. 函数体:遍历 i 后面的所有位置,看看谁能加到 i 这个元素的后面。统计所有情况下的最大值。
  3. 递归出口:因为我们是判断之后再进入递归的,因此没有出口~

记忆化搜索:

  1. 加上⼀个备忘录;
  2. 每次进入递归的时候,去备忘录里面看看;
  3. 每次返回的时候,将结果加入到备忘录里面。

动态规划:

  1. 递归含义 -> 状态表示;
  2. 函数体 -> 状态转移方程;
  3. 递归出口 -> 初始化。

🌴算法代码:

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

四、猜数字大小 II

1. 题目链接:375. 猜数字大小 II

2. 题目描述:

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

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

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

示例 1:

输入:n = 10
输出:16
解释:制胜策略如下:
- 数字范围是 [1,10] 。你先猜测数字为 7 。- 如果这是我选中的数字,你的总费用为 $0 。否则,你需要支付 $7 。- 如果我的数字更大,则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。- 如果这是我选中的数字,你的总费用为 $7 。否则,你需要支付 $9 。- 如果我的数字更大,那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏,总费用为 $7 + $9 = $16 。- 如果我的数字更小,那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏,总费用为 $7 + $9 = $16 。- 如果我的数字更小,则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。- 如果这是我选中的数字,你的总费用为 $7 。否则,你需要支付 $3 。- 如果我的数字更大,则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。- 如果这是我选中的数字,你的总费用为 $7 + $3 = $10 。否则,你需要支付 $5 。- 如果我的数字更大,那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏,总费用为 $7 + $3 + $5 = $15 。- 如果我的数字更小,那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏,总费用为 $7 + $3 + $5 = $15 。- 如果我的数字更小,则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。- 如果这是我选中的数字,你的总费用为 $7 + $3 = $10 。否则,你需要支付 $1 。- 如果我的数字更大,那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏,总费用为 $7 + $3 + $1 = $11 。
在最糟糕的情况下,你需要支付 $16 。因此,你只需要 $16 就可以确保自己赢得游戏。

示例 2:

输入:n = 1
输出:0
解释:只有一个可能的数字,所以你可以直接猜 1 并赢得游戏,无需支付任何费用。

示例 3:

输入:n = 2
输出:1
解释:有两个可能的数字 1 和 2 。
- 你可以先猜 1 。- 如果这是我选中的数字,你的总费用为 $0 。否则,你需要支付 $1 。- 如果我的数字更大,那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏,总费用为 $1 。
最糟糕的情况下,你需要支付 $1 。

提示:

  • 1 <= n <= 200

3. 解法:

🌴算法思路:

暴搜:

  1. 递归含义:给 dfs ⼀个使命,给他⼀个区间 [left, right] ,返回在这个区间上能完胜的最小费用;
  2. 函数体:选择 [left, right] 区间上的任意⼀个数作为头结点,然后递归分析左右子树。求出所有情况下的最小值;
  3. 递归出口:当 left >= right 的时候,直接返回 0 。

记忆化搜索:

  1. 加上一个备忘录;
  2. 每次进入递归的时候,去备忘录里面看看;
  3. 每次返回的时候,将结果加入到备忘录里面。

🌴算法代码:

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

五、矩阵中的最长递增路径

1. 题目链接:329. 矩阵中的最长递增路径

2. 题目描述:

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。

示例 1:

输入:matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出:4 
解释:最长递增路径为 [1, 2, 6, 9]。

示例 2:

输入:matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出:4 
解释:最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3:

输入:matrix = [[1]]
输出:1

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

3. 解法:

🌴算法思路:

暴搜:

  1. 递归含义:给 dfs ⼀个使命,给他⼀个下标 [i, j] ,返回从这个位置开始的最长递增路径的长度;
  2. 函数体:上下左右四个方向瞅⼀瞅,哪里能过去就过去,统计四个方向上的最大长度;
  3. 递归出口:因为我们是先判断再进入递归,因此没有出口~

记忆化搜索:

  1. 加上一个备忘录;
  2. 每次进入递归的时候,去备忘录里面看看;
  3. 每次返回的时候,将结果加入到备忘录里面。

🌴算法代码:

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

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

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

相关文章

【楚怡杯】职业院校技能大赛 “云计算应用” 赛项样题六

某企业根据自身业务需求&#xff0c;实施数字化转型&#xff0c;规划和建设数字化平台&#xff0c;平台聚焦“DevOps开发运维一体化”和“数据驱动产品开发”&#xff0c;拟采用开源OpenStack搭建企业内部私有云平台&#xff0c;开源Kubernetes搭建云原生服务平台&#xff0c;选…

涛思数据库安装和卸载

安装 cd opt/taos/TDengine-server-2.4.0.5 sudo ./install.sh 启动taos​ 安装后&#xff0c;请使用 systemctl 命令来启动 TDengine 的服务进程 systemctl start taosd检查服务是否正常工作&#xff1a; systemctl status taosd 升级 3.0 版在之前版本的基础上&#x…

使用 SpringBoot 基础web开发的支持

首先导入项目相关的依赖&#xff1a; pom.xml 文件&#xff1a; 导入相关项目依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-in…

Git使用—把当前仓库的一个分支push到另一个仓库的指定分支、基于当前仓库创建另一个仓库的分支并推送到对应仓库(mit6828)

把学习过程中遇到的Git问题汇总如下&#xff08;后续学习遇到问题会及时更新此专栏&#xff09;&#xff1a; Git原理及常用命令小结——实用版&#xff08;ing......&#xff09;、Git设置用户名邮箱-CSDN博客 解决git每次push代码到github都需要输入用户名以及密码-CSDN博客…

硬件工程师笔试面试——变压器

目录 9、变压器 9.1 基础 变压器原理图 变压器实物图 9.1.1 概念 9.1.2 变压器组成结构 9.1.3 变压器原理 9.1.4 变压器的类型 9.1.5 应用领域 9.2 相关问题 9.2.1 变压器的工作原理是什么? 9.2.2 如何选择合适的变压器类型? 9.2.3 变压器在实际应用中,如何进行…

9.18 C++对C的扩充

使用cout实现输出斐波那契前20项的值 #include <iostream>using namespace std;int main() {int n11,n21,n3;cout << n1 <<" "<< n2<<" ";for(int i0;i<18;i){n3n1n2;cout<<n3<<" " ;n1n2;n2n3;}…

算法备案究竟是自己做还是找专业机构?

算法备案究竟是自己做还是找专业机构&#xff1f; 在深入了解算法备案申报要求和规则的基础上&#xff0c;企业可以选择自行完成备案。然而&#xff0c;如果缺乏相关知识和经验&#xff0c;申报材料可能会反复出错&#xff0c;导致被驳回&#xff0c;增加试错的时间成本&#x…

前端开发之原型模式

介绍 原型模式本质就是借用一个已有的实例做原型&#xff0c;在这原型基础上快速复制出一个和原型一样的一个对象。 class CloneDemo {name clone democlone(): CloneDemo {return new CloneDemo()} } 原型原型链 函数&#xff08;class&#xff09;都有显示原型 prototyp…

录音翻译成文字的软件有哪些?试试这5款工具,一键识别

将录音翻译成文字的需求日益增长&#xff0c;无论是商务会议、学术讲座还是日常生活&#xff0c;一款高效、准确的录音翻译软件都能极大地提升我们的工作与生活效率。今天&#xff0c;我们就来盘点5款备受好评的录音翻译成文字的软件&#xff0c;一起来了解下吧。 工具一&#…

【云原生监控】Prometheus之PushGateway

Prometheus之PushGateway 文章目录 Prometheus之PushGateway介绍作用资源列表基础环境一、部署PushGateway1.1、下载软件包1.2、解压软件包1.3、编辑配置systemctl启动文件1.4、创建日志目录1.5、加载并启动1.6、监控端口1.7、访问PushGateway 二、 配置Prometheus抓取PushGate…

git push失败原因上传的文件超过了Gitee的上限100M

! [remote rejected] master -> master (pre-receive hook declined) error: failed to push some refs to 这个错误信息表明你在尝试将更改推送到Gitee的socket_service仓库时遇到了问题。具体来说&#xff0c;问题出在你尝试推送的文件大小超过了Gitee平台设定的限制。Git…

ES6标准---【八】【学习ES6看这一篇就够了!!!】

目录 前言 export命令 输出变量 输出函数/类 export中的as别名 export必须一一对应 export接口的响应性 注意 import命令 import命令的语法 import命令里的as别名 import的只读性 import命令具有提升性 import的一些约定 import的静态执行 import的唯一执行性 模…

前端常见面试-首页性能提升、项目优化

首页性能提升 Vue 首页性能提升是Vue应用开发中非常重要的一环&#xff0c;它直接影响用户体验和应用的加载速度。以下是一些关键的Vue首页性能提升策略&#xff1a; 1. 代码分割与懒加载 路由懒加载&#xff1a;利用Webpack的动态导入&#xff08;import()&#xff09;特性…

36.贪心算法3

1.坏了的计算器&#xff08;medium&#xff09; . - 力扣&#xff08;LeetCode&#xff09; 题目解析 算法原理 代码 class Solution {public int brokenCalc(int startValue, int target) {// 正难则反 贪⼼int ret 0;while (target > startValue) {if (target % 2 0…

在Word中,用VBA比较两段文本的相似度

效果1: 去掉字符串中回车&#xff0c;进行改进后效果&#xff1a; 代码&#xff1a; Function LevenshteinDistance(s As String, t As String) As IntegerDim d() As IntegerDim i As IntegerDim j As IntegerDim cost As IntegerDim sLen As IntegerDim tLen As IntegersLen…

【CSS in Depth 2 精译_034】5.4 Grid 网格布局的显示网格与隐式网格(下)

当前内容所在位置&#xff08;可进入专栏查看其他译好的章节内容&#xff09; 第一章 层叠、优先级与继承&#xff08;已完结&#xff09; 1.1 层叠1.2 继承1.3 特殊值1.4 简写属性1.5 CSS 渐进式增强技术1.6 本章小结 第二章 相对单位&#xff08;已完结&#xff09; 2.1 相对…

【网络通信基础与实践第二讲】包括互联网概述、互联网发展的三个阶段、互联网的组成、计算机网络的体系结构

一、互联网概述 计算机网络是由若干节点&#xff08;node&#xff09;和连接这些节点的链路&#xff08;link&#xff09;组成。 网络之间还可以通过路由器互联起来&#xff0c;这就构成了一个覆盖范围更大的计算机网络。这样的网络称为互联网。 网络把许多计算机连接在一起…

汽车行业智能化:驶向未来的快车道

在科技日新月异的今天&#xff0c;汽车行业正以前所未有的速度迈向智能化时代。从自动驾驶技术的不断升级&#xff0c;到智能座舱的丰富功能&#xff0c;再到车联网的广泛应用&#xff0c;汽车智能化的发展趋势正深刻地改变着我们的出行方式和生活。 一、自动驾驶&#xff1a;…

Etcd权限认证管理

1 查看是否开启权限认证 ctl auth status 2 开启权限认证 ctl auth enable。开启后每一条命令都要加上用户 --userroot:root(root默认最高权限) 3 创建其他用户 ctl user add user1 --user用户名:密码 4 创建角色 ctl role add testR --user 5 为角色添加权限 ctl role g…

Submariner 部署全过程

Submariner 部署全过程 部署集群配置 broker 集群&#xff1a; pod-cidr&#xff1a;11.244.0.0/16 service-cidr 11.96.0.0/12 broker 172.100.0.109 node 172.100.0.108 集群 1&#xff08; pve3 &#xff09;&#xff1a; pod-cidr&#xff1a;10.244.0.0/16 service-…