专题十三_记忆化搜索_算法专题详细总结

目录

1. 斐波那契数（easy）

那么这里就画出它的决策树 ：

解法一：递归暴搜

 解法二：记忆化搜索

解法三：动态规划

1.暴力解法（暴搜）

2.对优化解法的优化：把已经计算过的值存起来。

那么问题来了：

2. 不同路径（medium)

 解析：

解法一：暴力

解法二：记忆化搜索

添加备忘录：

解法三：随手改动态规划

3. 最⻓递增⼦序列（medium）

解析：

解法一：暴搜

决策树暴搜：dfs

记忆化暴搜：

解法二：记忆化搜索

解法三：动态规划

4. 猜数字⼤⼩II（medium）

解析：

解法一：暴搜dfs

解法二：记忆化搜索

其实大差不差，就是专门添加一个备忘录：

5. 矩阵中的最⻓递增路径（hard）

解法一：暴搜

解法二：记忆化搜索

总结一下吧~学到现在，递归章节也算是告一段落了，我个人的进步确实有了质的变化，我自己能感受到，对于这一专题，可以很明显的看出，在遇到重复子问题，并且求关于路径个数，最长长度，多少次数之类的问题，都是要对整个决策树进行完整的遍历和取最值，但是在遍历过程种都会遇到很多重复遍历的问题，对于这种重复遍历的问题的次数，我们只需要往动态规划方面考虑的思路，这里不同于前几个章节的直接深度优先遍历，利用visit数组来判断还需不需要进入下一层，那个属于floodfill算法，要求分块的面积或者分块的个数，所以还是要好好进行区分总结！！！

---

为了能引入记忆化搜索的概念和体现它的完美性，这里引入一个例题来进行描述：

1. 斐波那契数（easy）

斐波那契数列的引入，相比前面那些暴搜的题目还是要简单很多，但是也不能小看这一题的简单程度，一般难的题目总是有很多简单的小块来进行综合的，所以有这题引入可以分别解决关于

暴搜 -> 记忆化搜索 -> 动态规划 的过度,

那么这里就画出它的决策树 ：

这里通过这个决策树来求解斐波那契数列的暴力解就是不断的递归到最后一层，和就进行求解d[0] 和 d[1] 的值的大小：

解法一：递归暴搜

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);}
};

 虽然这里的暴搜过程十分简单，但是当我们看到这里的时间复杂度上，以及这个决策树上有着非常多的重复步骤，列入这个决策树上进行展开想求d[5]就得知道d[4]+d[3],依次类推，那么想知道d[4] 就又要知道d[3]+d[2] 那么这里就会有很多重复性的步骤，会让时间复杂度大大增加

那么在此基础上，我们只需要添加一个备忘录，让每次进行第一次递归的值能够存入到备忘录，那么只要后面再次遍历到该数的时候就能够直接得到该数，此时加入遍历的深度是O(N),那么就要递归n层在进行返回才能再次得到该值，但是如果采用记忆化搜索得到该值只需要在O(1)的时间内进行查找该值即可。

 解法二：记忆化搜索

什么是带备忘录的递归？只需要在O(1)时间内就能够再次得到该值；

如何实现记忆化：

1.添加一个备忘录   实现<可变参数，返回值>（就是 下标 跟 返回值 的映射）

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

3.在每次进入递归的时候，往备忘录里面瞅一瞅

那么实现备忘录就需要一个一维数组进行下标与返回值的映射即可：

memo[100];
这里要对memo数组进行初始化，初始化要对该数组实现在后面递归返回值存入时不会出现的数，保证不会出现并没有存入该值却被取出值的情况：

memset(memo,-1,sizeof(memo));

class Solution {
public:int memo[31];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) return n;memo[n]=dfs(n-1)+dfs(n-2);return memo[n];}
};

1.这里就要对全局变量添加一个备忘录，让后进行初始化为-1；

2.在入口处就要判断当前下标为n处是否在备忘录中出现过，若出现过就直接取走；否则就进行递归在后面第一次出现的时候进行添加；

3.因为只有在最后一层的时候有明确的返回值，这样遍历到最后一层可以直接进行返回；但是memo[n]在递归过程中第一次出现的结果全部都添加到备忘录内，这样就不会出现第二次递归到最后一层的结果，然后进行第一次添加后进行最后的返回该层的memo[n];

解法三：动态规划

从动态规划内的步骤可以看出动态规划与记忆化搜索都是一一对应的，也可以说记忆化搜索其实也就是另一种形式的普通动态规划。

动态规划 和 记忆化搜索的本质：

1.暴力解法（暴搜）

2.对优化解法的优化：把已经计算过的值存起来。

在《算法导论》里面：记忆化搜索 vs 常规动态规划 -> 统称为动态规划

                                           递归                地推(循环)

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

动态规划只要准备好状态转移方程就能够进行解答问题。

那么问题来了：

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

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

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

都是一回事

3.自顶向下 vs 自顶向上

所以对于记忆化搜索的问题，也就是说，在画出决策树或者递归展开图的时候，发现很多重复性的子递归，那么此时就用一个备忘录进行记录当前值，然后进行记录当前值，以便后续直接进行查找不用再次进行递归。

2. 不同路径（medium)

题目意思很简单，就是求出原点到右下角的所有路径个数

 解析：

随便找一个点，想要求出到达当前位置的所有路径个数，那么就是：

dfs(i,j)=dfs(i-1,j)+dfs(i,j-1);

那么原点这个位置就不能从(0,0)开始，要从(1,1) 开始。所以要为这个矩阵加一行一列。

那么当i==0 或者 j==0 的时候就都是不能成立的时候，因为在这上面都是不能满足条件的。 

解法一：暴力

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);}
};

 就只是利用暴搜的方式，但这个会超时，所以要对它进行记忆化改进。

解法二：记忆化搜索

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

添加备忘录：

1.就是在进入dfs的时候观察有没有满足已经存在备忘录的条件的值。

2.在当前值被返回之前存入备忘录；

解法三：随手改动态规划

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];}
};

可以看的出来，思路完全就是跟记忆化搜索大差不差，所以对于暴搜改记忆化，记忆化改动态规划简直不要太方便。

3. 最⻓递增⼦序列（medium）

题目意思就跟标题一样简单，只需要求出最长子序列即可。

解析：

解法一：暴搜

决策树暴搜：dfs

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

记忆化暴搜：

利用动态规划的思想，但是这是个决策树，要往记忆化的方向去靠近，那么就是从上往下的递归，然后求值并存入备忘录。这里只考虑暴搜的结果传入从i位置开始的结果，进去后开始考虑下一个值是选取哪一个位置的值，进行判断条件，因为进入dfs后当层的ret就都是要求出当前层ret的最大值：判断条件

if(nums[i]>nums[pos])；

因为dfs要返回当前层后面的最长子序列，所以用ret接受dfs的返回值：

 ret=max(ret,dfs(nums,i)+1);

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

那么这个暴搜绝对会超时，因为在整个非常大的树的时候，会进行完全展开，出现很多重复性的子问题，会对很多已经被展开的树再次进行展开，时间复杂度大大增加。

解法二：记忆化搜索

那么就要开始考虑记忆化搜索，来添加备忘录，这里memo弄成全局和传参都一个样，传参数也是要加引用&就相当于全局变量。

添加备忘录：

1.就是判断当前位置pos的值是否存在备忘录里面，这样直接去pos后面的最长的子序列长度。

2.ret还是照样要求出当前层的最大值，然后再最后返回ret的时候要对ret存入备忘录的操作，这样在后面再次要展开pos层的时候能直接再备忘录内找到。

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

解法三：动态规划

记忆化搜索改动态规划，其实再两个代码内可以看出是一一对应的，我们要求出当前位置的最长子序列就要通过最后面的值往前遍历，来从长度为1开始往前求，才能更好的求出dp[i]位置的长度。

那么当从最后一个数往前求的时候，唯一可以顾及到的就是当前数的后面的所有数。也就是当前位置的决策树。进行展开就是一个小的决策树。就是dp[i],dp[j]+1取最大值，此时的for(j)是从nums[i]后面的所有值开始的。

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[j]>nums[i]) dp[i]=max(dp[i],dp[j]+1);ret=max(ret,dp[i]);}return ret;}
};

4. 猜数字⼤⼩II（medium）

题目意思有点难理解，推荐直接往后看：

解析：

题目意思

玩这个游戏要准备的最少的本金，如果猜错了，就要给但钱猜错数字的前，求出最少需要多少前可以完全获得胜利，直到猜对为止。

那么为了找出最所要最少的钱，那么就要暴力的枚举所有情况，然后找出最少的钱能够获胜的时候：

那么画出决策树后，大概就是再一个区间随机选择一个数，让系统告诉我是大了，还是小了，如果大了就递归到下一层，再选择一个比上一层要小的值；如果小了，就到下一层选一个比上一层大的值。

然后进行返回到上一层【x，y】都是左子树或者右子树所需最小的钱，在对【x,y】取最大值，因为只有取了最大值，才能保证准备的钱满足所有的情况。

解法一：暴搜dfs

考虑两种边界条件，当i==1的时候，取【left , right】 -> [1,0] 这种取值范围不合法 直接返回0；

当i==2 的时候，取值范围是[left,right] -> [1,1] 说明已经只有最后一个值了，直接返回0，不用再往后继续进行取值。

if(left>=right) return 0;

暴搜：dfs(1,n) 传入可以随机取值的区间范围，然后进行猜数字游戏

猜出所有数字的情况，head作为头节点，如果大了，就定义x去[left,head-1]位置去找，如果小了就定义y去[head+1,right]区间去找，然后都返回的是两边的最小值，让用到的钱最小，然后对两边的值取最大max(x,y) 这样能保证，这个最小值里面的最大值可以让当前层的所有花费都被满足，但是当前层后续有很多种随机取值的方式，所以我们要考虑到最便宜的一种就是最后当前层随机取值的所有情况都要取min 

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(head+max(x,y),ret);}return ret;}
};

解法二：记忆化搜索

其实大差不差，就是专门添加一个备忘录：

只要写出来暴搜的过程，改成记忆化简直易如反掌

1.添加备忘录，然后判断当前值的取值范围[left][right]是否再备忘录内出现过？

2.每次再该层的取值范围进行返回前，先存入到备忘录内：

memo[left][right]=ret;

class Solution {
public:int memo[201][201];int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(left>=right) return 0;if(memo[left][right]) 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(head+max(x,y),ret);}memo[left][right]=ret;return ret;}
};

5. 矩阵中的最⻓递增路径（hard）

题目意思很简单，就是要求出任意一点出发能够找出的最长的递增路径的长度。

解析：

解法一：暴搜

 不用想肯定会超时，但是思路是简单的，只需要再主函数内任意传入一个位置的值，然后开始遍历上下左右，开始返回能够进入当前位置的最大长度，一直让ret取到当前位置的最大长度即可。

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

解法二：记忆化搜索

跟上面题目一样，只需要添加上备忘录：

1.进入dfs判断是否存在当前值再备忘录内，如果存在就直接返回，不存在就进行添加；

2.每次到dfs函数底部进行返回前，只需要将当前值进行存入即可。

class Solution {
public:int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int n,m;int memo[201][201];int longestIncreasingPath(vector<vector<int>>& matrix) {m=matrix.size(),n=matrix[0].size();int ret=0;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]) return memo[i][j];int ret=1;for(int k=0;k<4;k++){int x=dx[k]+i;int y=dy[k]+j;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;}
};

总结一下吧~学到现在，递归章节也算是告一段落了，我个人的进步确实有了质的变化，我自己能感受到，对于这一专题，可以很明显的看出，在遇到重复子问题，并且求关于路径个数，最长长度，多少次数之类的问题，都是要对整个决策树进行完整的遍历和取最值，但是在遍历过程种都会遇到很多重复遍历的问题，对于这种重复遍历的问题的次数，我们只需要往动态规划方面考虑的思路，这里不同于前几个章节的直接深度优先遍历，利用visit数组来判断还需不需要进入下一层，那个属于floodfill算法，要求分块的面积或者分块的个数，所以还是要好好进行区分总结！！！

希望对你也有帮助~