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

【递归，搜索与回溯算法】记忆化搜索（二）

news 2025/6/23 11:44:07

📝前言说明：

本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

点击链接	开始学习
导论	递归 (一) 、递归 (二)
二叉树的深搜	穷举 vs 暴搜 vs 深搜 vs 回溯 vs 剪枝
综合练习（一）	综合练习（二）
综合练习（三）	综合练习（四）
FloodFill（一）	FloodFill（二）
记忆化搜索（一）	记忆化搜索（二）

题单汇总链接：点击 → 题单汇总

题目

300. 最长递增子序列
- 优质解
375. 猜数字大小 II
- 优质解
329. 矩阵中的最长递增路径
- 个人解

300. 最长递增子序列

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
在这里插入图片描述

优质解

思路：

暴搜：以i位置为开始的最长递增子序列的长度
- 递归函数头：给一个pos返回以pos为开始的最长递增子序列的长度
- 最后对所有开始位置遍历一遍找到最大的
加记忆化搜搜

代码：

class Solution {
public:int dfs(vector<int>& nums, vector<int>& memo, int pos){if(memo[pos]) return memo[pos];int ret = 1; // 记录返回值（当子序列元素为 1 时，默认为 1）for(int i = pos + 1; i < nums.size(); i++) // 下一个元素{if(nums[i] > nums[pos])ret = max(ret, dfs(nums, memo, i) + 1);}memo[pos] = ret; // 加入备忘录return ret;}int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> memo(n);int ans = 1;for(int i = 0; i < n; i++){ans = max(ans, dfs(nums, memo, i));}return ans;}
};

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

375. 猜数字大小 II

题目链接：https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/
在这里插入图片描述

优质解

思路：

按区间来填充备忘录

代码：

class Solution {
public: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 = i + dfs(left, i - 1, memo);int r = i + dfs(i + 1, right, memo);// 找到所有选择中 最大值最小的ret = min(ret, max(l, r));}memo[left][right] = ret;return memo[left][right];}int getMoneyAmount(int n) {vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1));return dfs(1, n, memo);}
};

时间复杂度： $O(n^3)$
空间复杂度： $O(n^2)$

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

题目链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/
在这里插入图片描述

个人解

思路：

没啥好说的，常规暴搜 + 备忘录
不需要check数组，因为要求严格递增，所以天然无回路

用时：13:00
屎山代码：

class Solution {
public:int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n;// 以 pos 位置为开始，然后返回以该位置为开始的最长路径int dfs(vector<vector<int>>& matrix, vector<vector<int>>& memo, int x, int y){if(memo[x][y]) return memo[x][y];int ret = 1;for(int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i]; // 下一个位置if(nx < m && nx >= 0 && ny < n && ny >= 0 && matrix[x][y] < matrix[nx][ny])ret = max(ret, 1 + dfs(matrix, memo, nx, ny));}memo[x][y] = ret;return memo[x][y];}int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();vector<vector<int>> memo(m, vector<int>(n, 0));int ans = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++)ans = max(ans, dfs(matrix, memo, i, j));}return ans;}
};