【算法/学习】：记忆化搜索
【算法/学习】：记忆化搜索
🚀引言：
基本概念
记忆化搜索（Memoization Search）：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。
主要特点和应用场景包括：
- 避免重复计算： 记忆化搜索算法通过缓存已经计算过的结果，以避免对相同输入进行重复计算。这在递归算法中特别有用，因为递归往往会导致相同的子问题被反复解决。
- 提高效率： 通过保存中间计算结果，记忆化搜索算法能够大幅减少算法的时间复杂度，从指数级别降低到多项式级别。
动态规划： 记忆化搜索在动态规划中经常被使用。动态规划是一种解决优化问题的方法，通常包含递归和子问题重叠的特点。记忆化搜索能够避免重复计算，使得动态规划算法更加高效。 递归算法优化： 记忆化搜索主要用于优化递归算法。在递归调用中，如果存在相同的输入参数，记忆化搜索算法将直接返回已经计算过的结果，而不是重新执行计算。 应用于搜索问题： 记忆化搜索不仅用于动态规划，还可以应用于搜索问题，特别是深度优先搜索中的状态记忆。
经典的例子包括斐波那契数列的递归实现、图的最短路径问题中的递归搜索等。在实现记忆化搜索时，通常需要使用数据结构（如哈希表、数组等）来保存已经计算过的结果。
记忆化搜索和动态规划都是一种用于优化递归算法的技术，它们有很多相似之处，但也存在一些关键的区别
记忆化搜索与递归相同与不同
相同之处：
- 重叠子问题： 记忆化搜索和动态规划都针对具有重叠子问题性质的问题。这意味着问题可以被划分为许多相似的子问题，这些子问题在解决整体问题时会被多次重复计算。
- 优化递归： 两者都旨在优化递归算法。递归算法通常会导致相同的子问题被反复解决，而记忆化搜索和动态规划都致力于避免这种重复计算。
- 缓存中间结果： 记忆化搜索和动态规划都使用某种形式的缓存来存储已经计算过的中间结果，以便在需要时直接返回结果，而不是重新计算。
不同之处：
- 自顶向下 vs 自底向上： 记忆化搜索是自顶向下的方法，从大问题开始，逐步分解为子问题，并缓存这些子问题的结果。动态规划是自底向上的方法，从最小的子问题开始解决，逐步构建出整个问题的解。
- 递归 vs 迭代： 记忆化搜索通常使用递归实现，通过递归调用来解决问题。动态规划则使用迭代的方式，通过循环来计算并填充表格或数组。
- 状态转移方程 vs 递归调用： 在动态规划中，通常通过状态转移方程来描述问题的子问题之间的关系，从而构建解。而在记忆化搜索中，通常直接使用递归调用来表示问题的分解。
- 使用场景： 记忆化搜索通常更适用于处理问题的子问题规模较小，问题的状态转移方程比较复杂，递推关系不是很明确，问题适合转换为递归形式，并且递归深度不会太深。而动态规划则更适用于处理问题的子问题规模较大的情况，问题的状态转移方程比较简单，递归关系比较明确。问题不太适合转换为递归形式，或者递归深度过大容易导致栈溢出。
总的来说，当递归中出现了大量完全相同的问题时，就会用到记忆化搜索和动态规划去优化递归算法的技术，但它们的实现方式和问题解决的思路有一些不同。在解决问题时，根据具体的情况选择使用记忆化搜索或动态规划能够更好地满足问题的需求。
记忆化搜索的解题步骤
我们在使用记忆化搜索解决问题的时候，其基本步骤如下：
- 写出问题的动态规划「状态」和「状态转移方程」。
- 定义一个缓存（数组或哈希表），用于保存子问题的解。
- 定义一个递归函数，用于解决问题。在递归函数中，首先检查缓存中是否已经存在需要计算的结果，如果存在则直接返回结果，否则进行计算，并将结果存储到缓存中，再返回结果。
- 在主函数中，调用递归函数并返回结果。
让我们来看一些相关题目，加深对于记忆化搜索的理解吧
1. 斐波那契数
图解：
下面我们写出两种写法
递归写法：
int dfs(int n)
{
if (n == 0 || n == 1) return n;
return dfs(n - 1) + dfs(n - 2);
}
int fib(int n) {
return dfs(n);
}记忆化搜索写法：
int memo[31];
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 dfs(n - 1) + dfs(n - 2);
}
int fib(int n) {
//初始化为 -1
memset(memo, -1, sizeof memo);
return dfs(n);
}动态规划写法：
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];
}2. 不同路径
思路： 同样这里如果使用普通的递归深度遍历，会有大量重复计算导致时间复杂度过高，所以这里要使用记忆化搜索来辅助递归算法，达到线性的时间复杂度，我们计算每个格子的路径，相当于上面格子的路径加上左边格子的路径一直递推，完成递归的逆推，同样动态规划也是按照这个逻辑顺推过去 图解如下：
递归写法：（超时）
int dfs(int i, int j)
{
if (i == 0 || j == 0) return 0;
if (i == 1 && j == 1) return 1; // 起始位置（1，1）为1
return dfs(i - 1, j) + dfs(i, j - 1); // 只能往右下走
}
int uniquePaths(int m, int n) {
return dfs(m, n);
}记忆化搜索：
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 uniquePaths(int m, int n) {
vector<vector<int>> memo(m + 1, vector<int>(n + 1));
return dfs(m, n, memo);
}动态规划：
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
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];
}3. 最长递增子序列
思路： 暴力枚举每个起点，然后在每个起点的基础上往后枚举元素，然后记录最大长度即可 1、递归函数头 ：int (dfs pos)
- 返回以pos为起点最长递增子序列长度
2、递归函数函数体
- for(i = pos + 1 ~ n ) 找到 max( dfs(i) + 1 ） 即可
3、递归出口：该题不用递归出口，因为基本不会越界
递归写法：（超时）
int dfs(int pos, vector<int>& nums)
{
int ret = 1; // ret 初始化为 1,为一个字符时就是1
for (int i = pos + 1; i < nums.size(); i++) {
if (nums[i] > nums[pos]) { // 找到以 i 为起点的最大
ret = max(ret, dfs(i, nums) + 1);
}
}
return ret;
}
int lengthOfLIS(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++) // 以任意位置为起点的最大值
ret = max(ret, dfs(i, nums));
return ret;
}记忆化搜索：
int dfs(int pos, vector<int>& nums, vector<int>& memo)
{
if (memo[pos] != 0) return memo[pos]; //剪枝
int ret = 1; // ret 初始化为 1,为一个字符时就是1
for (int i = pos + 1; i < nums.size(); i++) {
if (nums[i] > nums[pos]) { // 找到以 i 为起点的最大
ret = max(ret, dfs(i, nums , memo) + 1);
}
}
memo[pos] = ret;
return ret;
}
int lengthOfLIS(vector<int>& nums) {
int ret = 0, n = nums.size();
vector<int> memo(n);
for (int i = 0; i < n; i++) // 以任意位置为起点的最大值
ret = max(ret, dfs(i, nums, memo));
return ret;
}动态规划：
int lengthOfLIS(vector<int>& nums) {
int n = nums.size(), ret = 0; //记录dp表内的最大值
//表示以某个位置为起点的最大值
vector<int> dp(n, 1); //初始为1
// 填表顺序：从后往前
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;
}4. 猜数字大小II
思路： 这里我们最简单的办法就是使用dfs暴力搜索每个猜数字的情况，在左右子树中找到较小的数累加，完成比对，加上记忆化搜索即可。
递归写法：（超时）
int dfs(int l, int r)
{
if (l >= r) return 0;
int ret = INT_MAX;
for (int head = l; head <= r; head++) //选择头节点
{
//获取当前以head为头节点左右子树的最大值，之所以获取最大值，是因为要确保自己能够获胜
int x = dfs(l, head - 1);
int y = dfs(head + 1, r);
ret = min(ret, head + max(x, y)); // 获胜的最小值
}
return ret;
}
int getMoneyAmount(int n) {
return dfs(1, n);
}记忆化搜索：
int memo[205][205];
int dfs(int l, int r){
if (l >= r) return 0;
if (memo[l][r] != 0) return memo[l][r]; //表示已经遍历过了
int ret = INT_MAX;
for (int head = l; head <= r; head++) //选择头节点
{
//获取当前以head为头节点左右子树的最大值，之所以获取最大值，是因为要确保自己能够获胜
int x = dfs(l, head - 1);
int y = dfs(head + 1, r);
ret = min(ret, head + max(x, y)); // 获胜的最小值
}
memo[l][r] = ret;
return ret;
}
int getMoneyAmount(int n) {
return dfs(1, n);
}5. 矩阵中的最长递增路径
思路： Dfs：从一个单元格开始进行深度优先搜索，即可找到从该单元格开始的最长递增路径。对每个单元格分别进行深度优先搜索之后，即可得到矩阵中的最长递增路径的长度。 具体可参考 【算法/学习】：flood算法-CSDN博客 但是这题如果仅仅使用 朴素深度优先搜索就会超时，因为进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，故可用记忆化的方法进行优化。用矩阵 memo 作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。 记忆化深度优先搜索：当访问到一个单元格 (i,j) 时，如果 memo[i][j]=0，说明该单元格的结果已经计算过，则直接从缓存中读取结果，如果 memo[i][j]=0，说明该单元格的结果尚未被计算过，则进行搜索，并将计算得到的结果存入缓存中。
递归写法：（超时）
int n, m;
int dir[4][2] = {
{-1,0},{1,0},{0,-1},{0,1}
};
int dfs(vector<vector<int>>& matrix, int i, int j) {
int ret = 1;
for (int k = 0; k < 4; k++) {
int x = i + dir[k][0], y = j + dir[k][1];
if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
ret = max(ret, dfs(matrix, x, y) + 1);
}
}
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;
}记忆化搜索：
int memo[205][205];
int n, m;
int dir[4][2] = {
{-1,0},{1,0},{0,-1},{0,1}
};
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 + dir[k][0], y = j + dir[k][1];
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 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;
}腾讯云开发者
