记忆化搜索（5题）

是什么？ 是一个带备忘录的递归

如何实现记忆化搜索

1.添加一个备忘录（建立一个可变参数和返回值的映射关系）

2.递归每次返回的时候把结果放到备忘录里

3.在每次进入递归的时候往备忘录里面看看。

目录

1.斐波那契数列

2.不同路径

3.最长递增子序列

4.猜数字大小2

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

1.斐波那契数列

LCR 126. 斐波那契数 - 力扣（LeetCode）

我们再看看动态规划的做法。我们发现其实两者具有一一对应的关系，只不过一种是用递归形式呈现，另一种是用递推形式呈现

小问题：

1. 所有的递归（暴搜、深搜），都能改成记忆化搜索吗？

不是的，只有在递归的过程中，出现了大量完全相同的问题时，才能用记忆化搜索的方式优化

2.带备忘录的递归vs动态规划 vs记忆化搜索

本质上是一回事

3.自顶向下 vs 自低向上

不同的看待问题的方式

4.暴搜->记忆化搜索->动态规划

可以为我们的动态规划提供一个方向

我们创建一个备忘录的时候需要在里面填入一个不可能取到的值，以此来判断备忘录是否已经更新

class Solution { public: int memo[110];//一个备忘录 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 == 1) { memo[1] = 1; return memo[1];//返回之前把值存到备忘录里面 } else if(n == 0) { memo[0] = 0; return memo[0]; } else { memo[n] = (dfs(n-1) + dfs(n - 2))%1000000007; return memo[n]; } } };

2.不同路径

62. 不同路径 - 力扣（LeetCode）

1.暴力搜索（会超时）

class Solution { public: int uniquePaths(int m, int n) { return dfs(m,n); } int dfs(int i, int j) { if(i == 0 || j == 0)return 0; if(i == 1 && j == 1)return 1; return dfs(i - 1, j) + dfs(i, j - 1); } };

2.记忆化搜索

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

3.最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

1.暴搜（会超时）

dfs（pos）的任务是返回以nums[pos]为开头的最长子序列

我们在主函数里面从头开始遍历一次，找到最大的那个，ret 一开始为0.

在dfs函数中，ret一开始为1，因为已经进入dfs函数的情况下最少也有一个数。

我们从pos的下一位开始，遍历到结尾，每遍历到一个位置我们判断这个值是否比nums【i】大，如果更大说明它可以连接到nums【i】后面，我们再更新ret， ret = max(ret, dfs(nums, i) + 1);

class Solution { public: int n; int lengthOfLIS(vector<int>& nums) { int ret = 0; n = nums.size(); for(int i = 0; i < n; i++) { ret = max(dfs(nums, i), ret); } return ret; } int dfs(vector<int>& nums, int pos) { int ret = 1; for(int i = pos + 1; i < n; i++) { if(nums[i] > nums[pos]) { ret = max(ret, dfs(nums, i) + 1); } } return ret; } };

2.记忆化搜索

记录数据需要在返回之前记录。

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

3.递归代码

dp[i]表示的是从i下标开始最大的一个子序列。

因此我们从末尾开始填dp表，每个位置最小的子序列是自身，因此dp表每个位置先赋值为1.

每次进行比较之后才更新

if(nums[i] < nums[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}

最后的结果从dp表里面挑一个最大的即可。

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

4.猜数字大小2

375. 猜数字大小 II - 力扣（LeetCode）

1.暴搜（会超时）

这题让我们求不管猜的是哪个数字确保获胜的最小金额

首先，猜的策略有很多种，我们用暴力搜索，从小到大依次以某个值为根，然后分出两个树，继续对两个树进行相同的操作。

我们要确保无论它让我们猜哪个值都要获胜，那么就应该找每棵树里面花钱最多的策略，

我们使得int l = dfs(left,i - 1);
int r = dfs(i + 1, right);

花钱最多的 即根节点+ 左右两树中花钱多的即 i + max(l, r) ，

同时又要最少金额，那么就从各种一定会获胜的金额中取出最小的即可

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 i = left; i <= right; i++) { int l = dfs(left,i - 1); int r = dfs(i + 1, right); ret = min(ret, i + max(l, r)); } return ret; } };

2.记忆化搜索

class Solution { public: int getMoneyAmount(int n) { vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1)); return dfs(1, n, memo); } 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 = dfs(left,i - 1, memo); int r = dfs(i + 1, right, memo); ret = min(ret, i + max(l, r)); } memo[left][right] = ret; return ret; } };

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

LCR 112. 矩阵中的最长递增路径 - 力扣（LeetCode）

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