【算法】记忆化搜索

快乐的流畅：个人主页

个人专栏：《算法神殿》《数据结构世界》《进击的C++》

远方有一堆篝火，在为久候之人燃烧！

---

引言

记忆化搜索，本质上是dfs + 备忘录，优化相同问题的搜索，极大提高算法效率。同时，记忆化搜索和普通的动态规划实际上是一样的，记忆化搜索是递归的形式，而动态规划是递推（循环）的形式。

一、不同路径

细节：

• 设置备忘录的时候扩大一圈，方便处理边界情况：mem.resize(m + 1, vector(n + 1))
• 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[i][j] != 0) return mem[i][j]
• dfs(i, j)：表示到(i, j)位置的路径数量
• dfs(i, j) = dfs(i - 1, j) + dfs(i, j - 1)
• 初始化：
  • if(i == 0 || j == 0) return 0
  • if(i == 1 && j == 1) mem[i][j] = 1，return 1
• 每次递归结束后，将结果存储在备忘录中：mem[i][j] = dfs(i, j - 1) + dfs(i - 1, j)
  

记忆化搜索版本

class Solution
{vector<vector<int>> mem;
public:int dfs(int i, int j){if(mem[i][j] != 0) return mem[i][j];if(i == 0 || j == 0) return 0;if(i == 1 && j == 1){mem[i][j] = 1;return 1;}mem[i][j] = dfs(i, j - 1) + dfs(i - 1, j);return mem[i][j];}int uniquePaths(int m, int n){mem.resize(m + 1, vector<int>(n + 1));return dfs(m, n);}
};

动态规划版本

class Solution
{
public: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];}
};

二、最长递增子序列

思路：

• 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[pos] != 0) return mem[pos]
• 递推关系式：（当前节点小于子节点时）当前节点的最大长度，是所有子节点中的最大长度 + 1
• dfs函数：返回以pos开头的最长递增子序列的长度
• 每次递归结束后，将结果存储在备忘录中：mem[pos] = len
  

记忆化搜索版本

class Solution
{vector<int> mem;int n;
public:int dfs(vector<int>& nums, int pos)//返回以pos开头的最长递增子序列的长度{if(mem[pos] != 0) return mem[pos];int len = 1;for(int i=pos+1; i<n; ++i){if(nums[pos] < nums[i]){len = max(len, dfs(nums, i) + 1);}}mem[pos] = len;return len;}int lengthOfLIS(vector<int>& nums){n = nums.size();mem.resize(n);int ret = 0;for(int i=0; i<n; ++i){ret = max(ret, dfs(nums, i));}return ret;}
};

动态规划版本

class Solution
{
public:int lengthOfLIS(vector<int>& nums){int n = nums.size();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[i] < nums[j]){dp[i] = max(dp[i], dp[j] + 1);}}ret = max(ret, dp[i]);}return ret;}
};

注意：记忆化搜索改动态规划，与直接动态规划的填表顺序不一样。

三、猜数字大小 ||

思路：

• 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[begin][end] != 0) return mem[begin][end]
• dfs函数：返回给定区间中获胜的最小金额
• 将begin到end这个大区间，分为两个区间
• 取两个区间中的最大金额，加上节点本身的金额，更新结果，取所有结果的最小值返回
• 每次递归结束后，将结果存储在备忘录中：mem[begin][end] = ret

class Solution
{int mem[201][201];
public:int dfs(int begin, int end){if(begin >= end) return 0;if(mem[begin][end] != 0) return mem[begin][end];int ret = INT_MAX;for(int i=begin; i<=end; ++i){int x = dfs(begin, i - 1), y = dfs(i + 1, end);ret = min(ret, i + max(x, y));}mem[begin][end] = ret;return ret;}int getMoneyAmount(int n){return dfs(1, n);}
};

四、矩阵中的最长递增路径

思路：

• 进入dfs递归，先看看备忘录是否存在该值，若存在则直接返回：if(mem[i][j] != 0) return mem[i][j]
• dfs函数：返回从(i, j)位置开始的最长递增路径的长度
• 递推关系式：（当下一个搜索的位置大于当前位置时）当前最长路径长度，为所有下一位置的最长长度的最大值 + 1
• 每次递归结束后，将结果存储在备忘录中：mem[i][j] = ret

class Solution
{int dx[4] = {1, -1, 0, 0};int dy[4] = {0, 0, 1, -1};int mem[201][201];int m, n;
public:int dfs(vector<vector<int>>& mat, int i, int j){if(mem[i][j] != 0) return mem[i][j];int ret = 1;for(int k=0; k<4; ++k){int x = i + dx[k], y = j + dy[k];if(x >= 0 && y >= 0 && x < m && y < n&& mat[x][y] > mat[i][j]){ret = max(ret, dfs(mat, x, y) + 1);}}mem[i][j] = ret;return ret;}int longestIncreasingPath(vector<vector<int>>& mat){m = mat.size(), n = mat[0].size();int ret = 0;for(int i=0; i<m; ++i){for(int j=0; j<n; ++j){ret = max(ret, dfs(mat, i, j));}}return ret;}
};

总结

记忆化搜索，主要难在递推关系式的推导，以及边界情况的把控，因为其本质就是动态规划。

当然，并不是所有题都很方便将记忆化搜索和动态规划相互转换，有些题写成记忆化搜索比较简单，有些题写成动态规划比较简单，因题而异。

真诚点赞，手有余香