记忆化搜索（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;
}
};