【递归、回溯专题（三）】记忆化搜索题集

2024-09-04 07:52
文章标签 搜索 递归 记忆 专题 回溯 题集

本文主要是介绍【递归、回溯专题（三）】记忆化搜索题集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1. 斐波那契数
  • 2. 不同路径
  • 2. 不同路径
  • 3. 最长递增子序列
  • 4. 猜数字大小II

1. 斐波那契数

斐波那契数 （通常用 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

解法一：递归
时间复杂度是O(N2)
以n=5为例对应的递归展开图如下，
在这里插入图片描述

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

解法二：记忆化搜索
记忆化搜索：在递归过程中遇到一些完全相同的问题，将完全相同的问题记录在备忘录中，等到下一次遇到了相同的问题直接去备忘录取值，无需再进行深度优先遍历。记忆化搜索又称为带备忘录的递归。
在这里插入图片描述实现记忆化搜索的步骤：

  1. 创建一个备忘录
  2. 递归每次返回之前，先将结果添加到备忘录中
  3. 在每次进入递归的时候，查找备忘录中是否存在即将要递归的值

时间复杂度：O(N)

class Solution {
public:int memory[31]; // 备忘录int fib(int n) {// 初始化备忘录的值为-1, -1的含义是指当前的斐波那契数未被计算memset(memory, -1, sizeof memory);return dfs(n);}int dfs(int n){// 进入递归之前要先查找备忘录if(memory[n] != -1) // 不等于-1代表之前处理过相同的问题return memory[n]; // 剪枝// 返回之前要先添加在备忘录if(n <= 1){memory[n] = n;return n;}// 返回之前要先添加在备忘录memory[n] = dfs(n-1) + dfs(n-2);return memory[n];}
};

解法三：动态规划
细节问题详见动态规划章节。
时间复杂度：O(N)

class Solution {
public:int fib(int n) {// 创建dp表int dp[31] = {0};// 初始化dp表dp[0] = 0, dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

问题讨论

  1. 记忆化搜索和动态规划的关系，在《算法导论》这本书中一起被归纳为动态规划。它们都是暴力搜索，都是将已经计算好了的值存起来；只不过记忆化搜索是递归的形式，而常规的动态规划是递推的形式。
  2. 并不是所有的递归(深搜、暴搜)，都可以改写成记忆化搜索，因为记忆化搜索处理的是递归当中大量的重复问题。

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

记忆化搜索解法：

2. 不同路径

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

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

问总共有多少条不同的路径？
在这里插入图片描述
算法原理：

  1. 备忘录表的设计
    大小为m+1,n+1. 因为题目要到达下标(m,n)，所以标的大小要设计为m+1,n+1。
  2. 函数体的设计
    在主函数中调用dfs(m,n)，其含义是传入我要到达(m,n)时，有多少路径。
    在递归函数dfs中，递归结束标志是：
if(i == 0 || j == 0) return 0;// 含义是到达下标0位置有多少种方法，由于是非法位置(不会到达的位置)，所以设置为0
if(i == 1 && j == 1) return 1;// 到达下标(1,1)位置有多少种方法，因为是起点，所以就是一种方法

递归函数返回值，和动态规划一样，返回值是上边和左边的种类之和

dfs(i-1, j) + dfs(i, j-1);

在这里插入图片描述

  1. 能否记忆化搜索？
    记忆化搜索就是在返回之前要将结果记录在备忘录。
    答案是能，因为递归会出现重复相同的操作
    在这里插入图片描述

暴力解法：
暴力解法会超时

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);
}
int uniquePaths(int m, int n) {return dfs(m, n);
}

记忆化搜索：
记忆化搜索是由暴力解法改写来的。

int dfs(vector<vector<int>> &memory, int i, int j)
{// 递归出口 if(i == 0 || j == 0) return 0;if(i == 1 && j == 1) {memory[1][1] = 1;return 1;}// 查找备忘录中是否已经填入了, 判断是否需要递归下去if(memory[i][j] != -1) return memory[i][j]; // 剪枝// 返回之前记录返回值在备忘录中memory[i][j] = dfs(memory, i-1, j) + dfs(memory, i, j-1);return memory[i][j];
}
int uniquePaths(int m, int n) {vector<vector<int>> memory(m + 1, vector<int>(n + 1, -1));return dfs(memory, m, n);
}

动态规划版本：
dp数组的含义：到达下标(i, j)一共有多少种方法。

int uniquePaths(int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 加1加的是虚拟节点// 初始化dp数组dp[0][1] = 1;// 遍历dp数组for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = dp[i][j-1] + dp[i-1][j];return dp[m][n];
}

3. 最长递增子序列

算法原理：
以一个数为子序列的起始位置，去它的后面找：
在这里插入图片描述
根据上图编写代码：
但是会超出时间限制，原因就是因为出现了很多重复的递归操作。

int lengthOfLIS(vector<int>& nums) 
{int ret = 0;for(int i = 0; i < nums.size(); i++){// 以第i个元素开头的递增子序列ret = max(ret, dfs(nums, i)); // 取以每个元素为开头递归返回来的递增子序列最大长度}return ret;
}
int dfs(vector<int>& nums, int pos)
{int ret = 1; // 这里ret要初始化为1, 因为如果ret没有被更新, 那么要返回当前节点的数目1// 在pos的后面选一个数构成子序列for(int i = pos + 1; i < nums.size(); i++){if(nums[i] > nums[pos]){ret = max(ret, dfs(nums, i) + 1); // +1代表将该节点本身加上去}}return ret;
}

记忆化搜索：
在这里插入图片描述

int memo[2501] = {0}; // 备忘录, 存放以i位置为开头的递增子序列长度
int lengthOfLIS(vector<int>& nums) 
{int n = nums.size();int ret = 0;for(int i = 0; i < n; i++){// 以第i个元素开头的递增子序列ret = max(ret, dfs(nums, i));}return ret;
}
int dfs(vector<int>& nums, int pos)
{if(memo[pos] != 0) return memo[pos];int ret = 1; // 这里ret要初始化为1, 因为如果ret没有被更新, 那么要返回当前节点的数目1// 在pos的后面选一个数构成子序列for(int i = pos + 1; i < nums.size(); i++){if(nums[i] > nums[pos]){ret = max(ret, dfs(nums, i) + 1); // +1代表将该节点本身加上去}}memo[pos] = ret;return ret;
}

动态规划版本：

  • dp数组的含义：dp[i]表示以i位置为起点的最长递增子序列的长度
  • 填表顺序：从后往前
    在之前的递归中递归是遍历到了只有一个元素或者元素中不构成升序就返回，也就是说返回是从后往前的。在动态规划当中，我们应从dp表的最后一个元素开始填，从后往前填。
int lengthOfLIS(vector<int>& nums) 
{int n = nums.size();vector<int> dp(n, 1); // 代表一个元素构成子序列时长度为1int ret = 0; // 找dp表的最大值// 填写dp表for(int i = n - 1; i >= 0; i--) // 找以i位置为开头的最长子序列长度{for(int j = i + 1; j < n; j++) // 从i的后面寻找子序列{if(nums[i] < nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;
}

4. 猜数字大小II

在这里插入图片描述在这里插入图片描述在这里插入图片描述

算法原理：
在这里插入图片描述

暴力枚举所有情况：
但是会超时。

int dfs(int left, int right)
{// 遇到叶子结点即为获胜if(left >= right) return 0;int ret = INT_MAX; // 用于存储获胜的最小现金数// 从区间[left,right]选择头节点for(int h = left; h <= right; h++){// lowerint l = dfs(left, h - 1);// higherint r = dfs(h + 1, right);// 为确保获胜的最大现金数为int chmp = max(l, r) + h;// 已经确保了区间[left,right]为头节点的子树组成的情况获胜, 但目前需要最少的钱ret = min(ret, chmp);}return ret;
}
int getMoneyAmount(int n) {return dfs(1, n);
}

记忆化搜索能否实现？答案是能
在这里插入图片描述记忆化搜索：

class Solution {
public:int memo[201][201];int dfs(int left, int right){// 遇到叶子结点即为获胜if(left >= right) return 0;// 判断区间[left,right]是否需要递归下去if(memo[left][right] != 0) return memo[left][right];int ret = INT_MAX; // 用于存储获胜的最小现金数// 从区间[left,right]选择头节点for(int h = left; h <= right; h++){// lowerint l = dfs(left, h - 1);// higherint r = dfs(h + 1, right);// 为确保获胜的最大现金数为int chmp = max(l, r) + h;// 已经确保了区间[left,right]为头节点的子树组成的情况获胜, 但目前需要最少的钱ret = min(ret, chmp);}// 记录区间的返回值memo[left][right] = ret;return ret;}int getMoneyAmount(int n) {return dfs(1, n);}
};

暴力搜索：会超时
注意一下，这题可以不加vis数组，因为vis数组主要是处理重复元素问题的，但我这里找的是递增序列，往回找时不会再次重复进入dfs。
在这里插入图片描述

class Solution {
public:int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};int m, n;int dfs(vector<vector<int>>& matrix, int i, int j){// 记录4个方向的最长路径int ret = 1;// 4个方向的dfsfor(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];int count = 0; // 记录一个方向能走多远if(x >= 0 && x < m && y >= 0 && y < n&& matrix[i][j] < matrix[x][y]){count = dfs(matrix, x, y) + 1;}ret = max(ret, count);}// 走到了尽头, count不会被更新return ret;}int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();int ret = 0;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)ret = max(ret, dfs(matrix, i, j));return ret;}
};

记忆化搜索：
尝试用一下记忆化搜索。首先我们看一下如果以1为起点进行dfs，和以6为起点进行dfs是不是有重复的dfs动作。那么以6为起点的路径就直接返回得到结果就行，无需再进行dfs了。
在这里插入图片描述

class Solution {
public:int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};int memo[201][201];int m, n;int dfs(vector<vector<int>>& matrix, int i, int j){// 以(i,j)这个位置为起点的路径之前已经搜索过了if(memo[i][j] != -1) return memo[i][j];// 记录4个方向的最长路径int ret = 1;// 4个方向的dfsfor(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];int count = 0; // 记录一个方向能走多远if(x >= 0 && x < m && y >= 0 && y < n&& matrix[i][j] < matrix[x][y]){count = dfs(matrix, x, y) + 1;}ret = max(ret, count);}// 走到了尽头, count不会被更新memo[i][j] = ret; // 记录在备忘录return ret;}int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();memset(memo, -1, sizeof(memo)); // 初始化备忘录int ret = 0; // 结果for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)ret = max(ret, dfs(matrix, i, j));return ret;}
};

这篇关于【递归、回溯专题（三）】记忆化搜索题集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1135429。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...
AI基础 L9 Local Search II 局部搜索

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态，生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案，则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时，算法停止。 — Choose k successors randomly, biased towards good ones — Close
阅读更多...
hdu4277搜索

hdu4277搜索

给你n个有长度的线段，问如果用上所有的线段来拼1个三角形，最多能拼出多少种不同的？ import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;
阅读更多...
音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

音视频入门基础：WAV专题（10）——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础：WAV专题（6）——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道，通过FFprobe命令可以打印WAV音频文件每个packet（也称为数据包或多媒体包）的信息，这些信息包含该packet的pts、dts： 打印出来的“pts”实际是AVPacket结构体中的成员变量pts，是以AVStream->time_base为单位的显
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
专题二_滑动窗口_算法专题详细总结

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口，引入： 滑动窗口，本质：就是同向双指针； 1.⻓度最⼩的⼦数组（medium） 1.解析：给我们一个数组nums，要我们找出最小子数组的和==target，首先想到的就是暴力解法 1）暴力： 2）优化，滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串（medium） 1）仍然是暴力解法： 2）优化： 进窗口：hash[s[rig
阅读更多...
回溯——9.全排列

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模：题目要求给出一个数组的所有排列组合，属于典型的全排列问题，这可以用回溯法来解决。回溯法通过递归的方式，依次将数组中的每个元素放入排列中，直到生成
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2