【递归、搜索与回溯算法】(掌握记忆化搜索的核心套路)-CSDN博客
在算法学习的过程中,递归、搜索与回溯几乎是每位学习者都绕不开的核心主题.它们不仅频繁出现在基础题和面试题中,也是理解更高级算法思想的重要入口.很多看似复杂的问题,拆开之后,本质上都是在一棵"决策树"上不断尝试、回退、剪枝,最终找到答案.不过,真正让不少人感到困惑的,并不是递归本身,而是:什么时候该搜索,什么时候该回溯,什么时候又该引入记忆化搜索来优化？“同样是"从一个状态出发不断往下尝试”,有些题直接暴力递归就能解决,有些题却会因为大量重复计算而效率极低.这时候,记忆化搜索就成了连接"暴力搜索"和"动态规划"之间的一座桥梁.可以说,掌握记忆化搜索的核心套路,不仅能帮助我们更高效地解决递归类问题,也能让我们对状态设计、重复子问题、搜索剪枝等关键思想形成更系统的理解.它不是单纯的"加一个缓存"这么简单,而是一种帮助我们从"会写递归"走向"会优化搜索"的思维升级.本文将围绕递归、搜索与回溯算法展开,重点讲清楚记忆化搜索的本质、适用场景与通用解题模板,帮助你真正建立起一套可迁移、可复用的解题框架.废话不多说,下面跟着小编的节奏一起去疯狂的学习吧!
1. 记忆 化搜索的算法思想背景
在正式理解记忆化搜索之前,我们要先明白一个很关键的问题:为什么普通递归会慢?很多初学者第一次接触递归时,往往会觉得这种写法很优雅.因为它天然符合"把大问题拆成小问题"的思考方式:一个问题如果可以由若干个更小的同 类 问题组成,那么就可以先定义递归函数,再不断向下求解,直到触达边界条件.这种思想本身没有问题,问题出在——重复计算.
举个最经典的例子,假设我们用递归去求斐波那契数列.为了计算f(n),我们需要先计算f(n-1)和f(n-2);而在计算 f(n-1) 的过程中,又会继续计算 f(n-2) 和 f(n-3).这样一来,像 f(n-2) 这样的子问题就会被反复求解很多次.随着n的增大,这种重复会迅速膨胀,最终让时间复杂度呈指数级增长.
这说明了一个重要事实：
很多递归问题并不是不能做,而是"做了太多遍同样的事".
而记忆化搜索的出现,本质上就是为了解决这个问题.
从"暴力展开"到"结果复用"
记忆化搜索的核心思想并不复杂,可以概括成一句话:每个状态只计算一次,算过的结果直接保存,下次再遇到时直接返回.也就是说,递归仍然保留,搜索过程也仍然存在,但我们不再让程序无休止地重复进入同一个子问题.第一次算出答案后,就把它"记住".以后只要搜索再次来到这个状态,就不必重新展开递归树,而是直接取出之前保存的结果.这就是"记忆化"三个字的含义:让算法拥有"记住过去"的能力.
从思想上看,它其实是在暴力搜索的基础上加入了一层" 缓存 机制",从而把原本大量重复的计算折叠掉.于是,一棵原本会疯狂生长的递归树,被压缩成了一张更有结构的"状态图".
记忆化搜索背后的适用前提
并不是所有递归都适合记忆化搜索.它之所以成立,通常依赖两个前提:
问题具有最优子结构或可拆分结构.
也就是说,大问题的答案可以通过若干个小问题的答案组合得到.
问题中存在重复子问题.
如果每次递归都会走到完全不同的状态,没有任何重复,那就没有"记住"的必要,缓存也起不到优化作用.所以,记忆化搜索最典型的使用场景,就是那些"递归很好想,但直接写会超时"的题目.比如:
斐波那契数列
爬楼梯
网格路径问题
字符串拆分
背包类搜索问题
区间递归问题
博弈型状态搜索问题
这些题目的共同点都是：状态会重复出现,而重复状态的答案又是固定的.
本质总结
如果用一句更凝练的话来概括,记忆化搜索的算法思想背景就是：它诞生于暴力递归的低效之中,本质是用"空间换时间"的方式,消除搜索过程中的重复计算.它既继承了递归"自顶向下、天然分解问题"的直观性,又吸收了动态规划"保存状态、复用结果"的高效性.因此,它不是一个孤立的技巧,而是一种非常重要的算法过渡思想.
2.斐波那契数(OJ题)
算法思路:解法(暴搜 -> 记忆化搜索 -> 动态规划):
暴搜：
a. 递归含义：给 dfs 一个使命,给他一个数 n,返回第 n 个斐波那契数的值;
b. 函数体：斐波那契数的递推公式;
c. 递归出口：当 n == 0 或者 n == 1 时,不用套公式.
记忆化搜索：
a. 加上一个备忘录;
b. 每次进入递归的时候,去备忘录里面看看;
c. 每次返回的时候,将结果加入到备忘录里面.
动态规划：
a. 递归含义 -> 状态表示;
b. 函数体 -> 状态转移方程;
c. 递归出口 -> 初始化.
核心代码
//全局数组：记忆化搜索的备忘录，存储已经计算过的斐波那契数，避免重复递归计算 int memo[31]; //全局数组：动态规划的dp数组，存储递推计算的斐波那契数 int dp[31]; //动态规划解法（迭代/自底向上）：计算斐波那契数列第n项 int fib(int n) { //初始化动态规划的基础条件：斐波那契第0项为0，第1项为1 dp[0] = 0; dp[1] = 1; //从第2项开始，循环递推计算到第n项 for(int i = 2; i <= n; i++) //核心递推公式：当前项 = 前一项 + 前两项 dp[i] = dp[i - 1] + dp[i - 2]; //返回最终计算的第n项斐波那契数 return dp[n]; } //记忆化搜索解法（递归+备忘录/自顶向下）：计算斐波那契数列第n项 int dfs(int n) { //第一步：检查备忘录，如果当前值已经计算过（不等于-1），直接返回结果 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]; } //主函数：测试两种解法 int main() { //记忆化搜索必须初始化！将备忘录全部赋值为-1，表示未计算 for(int i = 0; i < 31; i++){ memo[i] = -1; } //测试：计算斐波那契第10项 int n = 10; printf("动态规划计算结果：%d\n", fib(n)); printf("记忆化搜索计算结果：%d\n", dfs(n)); return 0; }
完整测试代码
#include <iostream> #include <cstring> using namespace std; int memo[31]; // 备忘录 int dp[31]; // 动态规划 int fib(int n) { dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[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]; } int main() { int n; cout << "请输入 n (0~30): "; cin >> n; if (n < 0 || n > 30) { cout << "输入范围错误，请输入 0~30 之间的整数。" << endl; return 0; } // 初始化 memo 数组为 -1 memset(memo, -1, sizeof(memo)); cout << "动态规划结果: " << fib(n) << endl; cout << "记忆化搜索结果: " << dfs(n) << endl; return 0; }
3.不同路径(OJ题)
算法思路:解法(暴搜 -> 记忆化搜索 -> 动态规划):
暴搜：
a. 递归含义：给 dfs 一个使命,给他一个下标,返回从 [0, 0] 位置走到 [i, j] 位置一共有多少种方法;
b. 函数体：只要知道到达上面位置的方法数以及到达左边位置的方法数,然后累加起来即可;
c. 递归出口：当下标越界的时候返回 0;当位于起点的时候,返回 1.
记忆化搜索:
a. 加上一个备忘录;
b. 每次进入递归的时候,去备忘录里面看看;
c. 每次返回的时候,将结果加入到备忘录里面.
动态规划:
a. 递归含义 -> 状态表示;
b. 函数体 -> 状态转移方程;
c. 递归出口 -> 初始化.
核心代码
class Solution { public: //主函数：入口，传入网格行数m、列数n，返回总路径数 int uniquePaths(int m, int n) { //方法1：动态规划（迭代/自底向上） //定义dp二维数组：dp[i][j] 表示从起点(1,1)到达位置(i,j)的路径总数 //数组大小 (m+1) x (n+1)，方便从1开始索引（对应网格坐标） vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //初始化起点：(1,1) 是起始位置，只有1种路径（原地不动） dp[1][1] = 1; //遍历网格所有行 i for(int i = 1; i <= m; i++) //遍历网格所有列 j for(int j = 1; j <= n; j++) { //跳过起点，因为起点已经初始化 if(i == 1 && j == 1) continue; //核心状态转移方程： //到达(i,j) 只能从 上方(i-1,j) 或 左方(i,j-1) 走过来 //所以路径数 = 上方路径数 + 左方路径数 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } //返回终点(m,n)的总路径数 return dp[m][n]; //方法2：记忆化搜索（递归/自顶向下） //定义备忘录数组：存储已计算的结果，避免重复递归 //vector<vector<int>> memo(m + 1, vector<int>(n + 1)); //调用递归函数，返回结果 //return dfs(m, n, memo); } //递归函数：记忆化搜索，计算从(1,1)到(i,j)的路径数 //memo：备忘录数组（引用传递，节省空间+同步修改） int dfs(int i, int j, vector<vector<int>>& memo) { //第一步：查备忘录！如果当前位置已经计算过，直接返回结果（剪枝，避免重复计算） if(memo[i][j] != 0) { return memo[i][j]; } //边界条件1：越界（行/列=0），没有路径，返回0 if(i == 0 || j == 0) return 0; //边界条件2：到达起点，路径数=1 if(i == 1 && j == 1) { memo[i][j] = 1; //存入备忘录 return 1; } //核心递归逻辑： //路径数 = 从上方来的路径 + 从左方来的路径 //计算后存入备忘录，方便后续直接调用 memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo); //返回当前位置的总路径数 return memo[i][j]; } };
完整测试代码
#include <iostream> #include <vector> using namespace std; class Solution { public: // 动态规划 int uniquePaths(int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); dp[1][1] = 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (i == 1 && j == 1) continue; dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m][n]; } // 记忆化搜索入口 int uniquePathsMemo(int m, int n) { vector<vector<int>> memo(m + 1, vector<int>(n + 1, 0)); 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 1; } memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo); return memo[i][j]; } }; int main() { Solution s; int m, n; cout << "请输入网格大小 m 和 n: "; cin >> m >> n; if (m <= 0 || n <= 0) { cout << "m 和 n 必须大于 0。" << endl; return 0; } int ans1 = s.uniquePaths(m, n); int ans2 = s.uniquePathsMemo(m, n); cout << "动态规划结果: " << ans1 << endl; cout << "记忆化搜索结果: " << ans2 << endl; return 0; }
4.最长递增子序列(OJ题)
算法思路:解法(暴搜 -> 记忆化搜索 -> 动态规划):
暴搜:
a. 递归含义：给 dfs 一个使命,给他一个数 i,返回以 i 位置为起点的最长递增子序列的长度;
b. 函数体：遍历 i 后面的所有位置,看看谁能加到 i 这个元素的后面.统计所有情况下的 最大值 .
c. 递归出口：因为我们是判断之后再进入递归的,因此没有出口~
记忆化搜索:
a. 加上一个备忘录;
b. 每次进入递归的时候,去备忘录里面看看;
c. 每次返回的时候,将结果加入到备忘录里面.
动态规划:
a. 递归含义 -> 状态表示;
b. 函数体 -> 状态转移方程;
c. 递归出口 -> 初始化.
核心代码
class Solution { public: //主函数：入口，传入数组nums，返回最长递增子序列长度 int lengthOfLIS(vector<int>& nums) { //方法1：动态规划（迭代/自底向上） //获取数组的长度 int n = nums.size(); //dp[i] 表示：以 nums[i] 为起点的最长递增子序列的长度 //初始化：每个元素自身就是一个长度为1的子序列，所以全部赋值为1 vector<int> dp(n, 1); //记录最终的答案（最长长度） int ret = 0; //填表顺序：从数组最后一个元素往前遍历（自底向上） for(int i = n - 1; i >= 0; i--) { //遍历 i 后面的所有元素 j for(int j = i + 1; j < n; j++) { //核心条件：nums[j] > nums[i]，满足严格递增 if(nums[j] > nums[i]) { //状态转移方程： //dp[i] = max(自身原值, 以j为起点的最长长度 + 1) dp[i] = max(dp[i], dp[j] + 1); } } //更新全局最大值，记录最长的子序列长度 ret = max(ret, dp[i]); } //返回最终结果 return ret; //方法2：记忆化搜索（递归/自顶向下） //备忘录数组：存储已经计算过的结果，避免重复递归 //vector<int> memo(n); //int ret = 0; //遍历数组每个位置，计算以该位置为起点的最长长度，取最大值 //for(int i = 0; i < n; i++) // ret = max(ret, dfs(i, nums, memo)); //return ret; } //递归函数：记忆化搜索，计算以 pos 位置为起点的最长递增子序列长度 //pos：当前遍历的数组下标 //nums：原数组（引用传递） //memo：备忘录数组（引用传递，缓存结果） int dfs(int pos, vector<int>& nums, vector<int>& memo) { //第一步：查备忘录！如果当前位置已经计算过，直接返回结果（剪枝优化） if(memo[pos] != 0) return memo[pos]; //初始化：当前元素自身长度为1 int ret = 1; //遍历 pos 后面的所有元素 for(int i = pos + 1; i < nums.size(); i++) { //满足严格递增，才能接在当前元素后面 if(nums[i] > nums[pos]) { //递归计算后续长度，更新最大值 ret = max(ret, dfs(i, nums, memo) + 1); } } //第二步：存备忘录！将计算结果存入，方便后续直接调用 memo[pos] = ret; //返回以pos为起点的最长递增子序列长度 return ret; } };
完整测试代码
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: // 动态规划 int lengthOfLIS(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 1); int ret = 0; // 填表顺序：从后往前 for (int i = n - 1; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (nums[j] > nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ret = max(ret, dp[i]); } return ret; } // 记忆化搜索入口 int lengthOfLISMemo(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> memo(n, 0); int ret = 0; for (int i = 0; i < n; i++) { ret = max(ret, dfs(i, nums, memo)); } return ret; } int dfs(int pos, vector<int>& nums, vector<int>& memo) { if (memo[pos] != 0) return memo[pos]; int ret = 1; for (int i = pos + 1; i < nums.size(); i++) { if (nums[i] > nums[pos]) { ret = max(ret, dfs(i, nums, memo) + 1); } } memo[pos] = ret; return ret; } }; int main() { Solution s; int n; cout << "请输入数组长度 n: "; cin >> n; if (n < 0) { cout << "数组长度不能为负数。" << endl; return 0; } vector<int> nums(n); cout << "请输入 " << n << " 个整数: "; for (int i = 0; i < n; i++) { cin >> nums[i]; } int ans1 = s.lengthOfLIS(nums); int ans2 = s.lengthOfLISMemo(nums); cout << "动态规划结果: " << ans1 << endl; cout << "记忆化搜索结果: " << ans2 << endl; return 0; }
5.猜数字大小||(OJ题)
算法思路:解法(暴搜 -> 记忆化搜索):
暴搜:
a. 递归含义：给 dfs 一个使命,给他一个区间 [left, right],返回在这个区间上能完胜的最小费用;
b. 函数体：选择 [left, right] 区间上的任意一个数作为头结点,然后递归分析左右子树.求出所有情况下的最小值;
c. 递归出口：当 left >= right 的时候,直接返回 0.
记忆化搜索:
a. 加上一个备忘录;
b. 每次进入递归的时候,去备忘录里面看看;
c. 每次返回的时候,将结果加入到备忘录里面.
核心代码
class Solution { // 备忘录数组：memo[left][right] 存储区间 [left, right] 内确保获胜的最小现金数 //题目 n 最大为 200，因此定义 201x201 覆盖所有区间 int memo[201][201]; public: //主函数：入口，传入数字上限 n，返回最终结果 int getMoneyAmount(int n) { //调用递归函数，计算区间 [1, n] 的最小获胜金额 return dfs(1, n); } //递归函数：记忆化搜索 //输入：区间 [left, right] //返回：在该区间内猜数字，确保获胜的最小现金数 int dfs(int left, int right) { //递归出口1：区间无效（左 >= 右） //说明区间只有1个数或没有数，不需要花钱猜测，直接返回0 if(left >= right) return 0; //递归出口2：查备忘录 //如果该区间的结果已经计算过，直接返回，避免重复递归（核心优化） if(memo[left][right] != 0) return memo[left][right]; //初始化结果为无穷大，用于后续找最小值 int ret = INT_MAX; //遍历区间内的每一个数字 head，尝试将其作为本次猜测的数字 for(int head = left; head <= right; head++) { //递归计算：选择 head 后，左区间 [left, head-1] 的最小花费 int x = dfs(left, head - 1); //递归计算：选择 head 后，右区间 [head+1, right] 的最小花费 int y = dfs(head + 1, right); //核心逻辑： //1.必须考虑最坏情况：max(x, y) → 保证能赢 //2.加上本次猜测的花费：head //3.取所有猜测方案中的最小值：min(ret, ...) ret = min(ret, head + max(x, y)); } //将计算好的结果存入备忘录，方便后续直接调用 memo[left][right] = ret; //返回当前区间 [left, right] 的最小获胜金额 return ret; } };
完整测试代码
#include <iostream> #include <cstring> #include <climits> using namespace std; class Solution { int memo[201][201]; public: int getMoneyAmount(int n) { memset(memo, 0, sizeof(memo)); // 初始化备忘录 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; } }; int main() { Solution s; int n; cout << "请输入 n: "; cin >> n; if (n <= 0 || n > 200) { cout << "n 的范围应为 1 ~ 200" << endl; return 0; } cout << "最少需要准备的钱数: " << s.getMoneyAmount(n) << endl; return 0; }
6.矩阵中的最长递增路径(OJ题)
算法思路:解法(暴搜 -> 记忆化搜索):
暴搜:
a. 递归含义：给 dfs 一个使命,给它一个下标 [i, j],返回从这个位置开始的最长递增路径的长度;
b. 函数体：上下左右四个方向瞅一瞅,哪里能过去就过去,统计四个方向上的最大长度;
c. 递归出口：因为我们是先判断再进入递归,因此没有出口~
记忆化搜索:
a. 加上一个备忘录;
b. 每次进入递归的时候,去备忘录里面看看;
c. 每次返回的时候,将结果加入到备忘录里面.
核心代码
class Solution { //备忘录数组：memo[left][right] 存储区间 [left, right] 内确保获胜的最小现金数 //题目 n 最大为 200，因此定义 201x201 覆盖所有区间 int memo[201][201]; public: //主函数：入口，传入数字上限 n，返回最终结果 int getMoneyAmount(int n) { //调用递归函数，计算区间 [1, n] 的最小获胜金额 return dfs(1, n); } //递归函数：记忆化搜索 //输入：区间 [left, right] //返回：在该区间内猜数字，确保获胜的最小现金数 int dfs(int left, int right) { //递归出口1：区间无效（左 >= 右） //说明区间只有1个数或没有数，不需要花钱猜测，直接返回0 if(left >= right) return 0; //递归出口2：查备忘录 //如果该区间的结果已经计算过，直接返回，避免重复递归（核心优化） if(memo[left][right] != 0) return memo[left][right]; //初始化结果为无穷大，用于后续找最小值 int ret = INT_MAX; //遍历区间内的每一个数字 head，尝试将其作为本次猜测的数字 for(int head = left; head <= right; head++) { //递归计算：选择 head 后，左区间 [left, head-1] 的最小花费 int x = dfs(left, head - 1); //递归计算：选择 head 后，右区间 [head+1, right] 的最小花费 int y = dfs(head + 1, right); //核心逻辑： //1.必须考虑最坏情况：max(x, y) → 保证能赢 //2.加上本次猜测的花费：head //3.取所有猜测方案中的最小值：min(ret, ...) ret = min(ret, head + max(x, y)); } //将计算好的结果存入备忘录，方便后续直接调用 memo[left][right] = ret; //返回当前区间 [left, right] 的最小获胜金额 return ret; } };
完整测试代码
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; 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) { if (matrix.empty() || matrix[0].empty()) return 0; memset(memo, 0, sizeof(memo)); 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; } }; int main() { int row, col; cout << "请输入矩阵的行数和列数: "; cin >> row >> col; if (row <= 0 || col <= 0 || row > 200 || col > 200) { cout << "行数和列数应在 1 ~ 200 之间。" << endl; return 0; } vector<vector<int>> matrix(row, vector<int>(col)); cout << "请输入矩阵元素：" << endl; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cin >> matrix[i][j]; } } Solution s; cout << "最长递增路径长度: " << s.longestIncreasingPath(matrix) << endl; return 0; }
