✨✨✨学习的道路很枯燥，希望我们能并肩走下来!
文章目录
目录
文章目录
前言
一 什么是记忆化搜索
二 相关题目练习
2.1 斐波那契数（详解记忆化搜索）
编辑 解法一（递归）：
解法二（记忆化搜索）：
解法三（动态规划）：
2.2 不同路径
2.3 最长递增子序列
2.4 猜数字大小II
2.5 矩阵中的最长递增路径
总结
前言
本篇详细介绍了进一步介绍记忆化搜索，让使用者对记忆化搜素有更加深刻的认知，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！
一 什么是记忆化搜索
记忆化搜索（Memoization Search）：是一种通过存储已经遍历过的状态信息，从而避免对同一状态重复遍历的搜索算法。
记忆化搜索是动态规划的一种实现方式。在记忆化搜索中，当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。
这样看概念可能有些抽象，接下来将用斐波那契数作为例子讲解
二 相关题目练习
2.1 斐波那契数（详解记忆化搜索）
509. 斐波那契数 - 力扣（LeetCode）
解法一（递归）：
class Solution {
public:int fib(int n) {return dfs(n);}int dfs(int n){if(n == 0 || n == 1) return n;return dfs(n-1) + dfs(n-2);}
};
从解法上看，这是一种低效的做法，时间复杂度为（2的n次方），那么为什么呢？
我们发现，递归的解法重复计算，导致效率低下！
那么我们可不可以用一个备忘录记录下重复计算的值呢？
解法二（记忆化搜索）：
class Solution {int memo[31]; //memory
public:int fib(int n) {memset(memo,-1,sizeof(memo));return dfs(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];}
};
解法三（动态规划）：
class Solution {int dp[31];
public: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.2 不同路径
62. 不同路径 - 力扣（LeetCode）
解法一：记忆化搜索
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> memo(m+1,vector<int>(n+1));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,j-1,memo) + dfs(i-1,j,memo);return memo[i][j];}
};解法二：动态规划
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];}
};2.3 最长递增子序列
300. 最长递增子序列 - 力扣（LeetCode）
解法一：记忆化搜索
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> memo(n);int ret = 0;for(int i = 0;i < n;i++)ret = max(ret,dfs(nums,i,memo));return ret;}int dfs(vector<int>& nums,int pos,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(nums,i,memo) + 1);}}memo[pos] = ret;return ret;}
};解法二：动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size(),ret = 0;vector<int> dp(n,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;}
};2.4 猜数字大小II
375. 猜数字大小 II - 力扣（LeetCode）
暴搜（超时）：
class Solution {
public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(left >= right) return 0;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));}return ret;}
};记忆化搜索：
class Solution {int memo[201][201];
public:int getMoneyAmount(int n) {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;}
};2.5 矩阵中的最长递增路径
329. 矩阵中的最长递增路径 - 力扣（LeetCode）
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) {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;}
};总结
✨✨✨各位读友，本篇分享到内容是否更好的让你理解记忆化搜索，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！
 "python API自动化(Requests库应用)")
