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