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

devtools/2024/9/25 5:36:02/

文章目录

  • 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.ppmy.cn/devtools/105570.html

相关文章

STL之my_list容器

STL之my_list容器

前言&#xff1a;各位老铁好久不见了&#xff0c;今天分享的知识是自己实现一个简单的list容器&#xff0c;为什么我先跳过vector容器的自我实现呢&#xff1f;我个人觉得vector相对于list的自我实现简单一点&#xff0c;所以今天先分享实现my_list的知识 我们要实现my_list&a…
阅读更多...
2023年最新JavaScript 基础面试题

2023年最新JavaScript 基础面试题

高级题目 实现一个异步队列 编写一个异步队列&#xff0c;支持添加任务和批量执行任务的功能。每个任务都是一个异步函数&#xff0c;队列需要保证任务按照添加的顺序执行。 class AsyncQueue { constructor() { // 你的代码 } enqueue(task) { // 你的代码 } start()…
阅读更多...
【leetcode刷题记录】二叉树遍历

【leetcode刷题记录】二叉树遍历

中序遍历 public List<Integer> inorderTraversal(TreeNode root) { // List<Integer> result new ArrayList<>(); // midAccTree(result,root); // return result;//栈迭代解决List<Integer> result new ArrayList<>()…
阅读更多...
Vue学习

Vue学习

概述 Vue.js&#xff08;读音 /vjuː/, 类似于 view&#xff09;是一个构建数据驱动的 web 界面的库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。 特点 Vue的核心是一个响应的数据绑定系统&#xff0c;它通过把标签和数据绑定来简化用户的操…
阅读更多...
域名证书，泛域名证书，sni

域名证书，泛域名证书，sni

文章目录 前言一、证书1.全域名证书2.泛域名证书 二、域名证书的使用1、浏览器请求域名证书流程对全域名证书的请求流程对泛域名证书的请求流程ssl client-hello携带server name 报文 2、浏览器对证书的验证流程 三、域名证书和sni 前言 本文介绍了泛域名证书和全域名证书的区别…
阅读更多...
Spring Boot 入门

Spring Boot 入门

1.1.1 什么是Spring Boot Spring Boot是一个开源的Java应用框架&#xff0c;由Pivotal团队提供&#xff0c;旨在简化Spring应用的初始搭建以及开发过程。‌ Spring Boot通过使用特定的配置方式&#xff0c;使得开发人员不再需要定义样板化的配置&#xff0c;从而在快速应用开发…
阅读更多...
使用 Pandas 进行数据可视化：全面指南（六）

使用 Pandas 进行数据可视化：全面指南（六）

在数据分析的过程中，数据的可视化是一个至关重要的环节。通过图形展示数据，不仅能够帮助我们直观地理解数据，还能够揭示数据背后的规律和趋势。Pandas 作为 Python 生态系统中强大的数据分析库，不仅提供了数据处理和分析的功能，还内置了方便易用的可视化方法。本文将详细介…
阅读更多...
k8s-pod 实战六 （如何在不同的部署环境中调整startupprobe的参数？）

k8s-pod 实战六 （如何在不同的部署环境中调整startupprobe的参数？）

在不同的部署环境中（如开发、测试、生产环境），你可能希望对 startupProbe 的参数进行调整，以适应不同的需求和条件。以下是几种常见的方法和实践： 方法一：使用 Kustomize 1. 目录结构 假设你的项目目录结构如下： my-app/ ├── base/ │ └── deployment.yaml …
阅读更多...
最新文章

Copyright @ 2022~2023