记忆化搜索专题篇

目录

斐波那契数

不同路径

最长递增子序列

猜数字大小II

矩阵中的最长递增路径

---

声明：下面将主要使用递归+记忆化搜索来解决问题！！！

斐波那契数

题目

思路

斐波那契数的特点就是除了第一个数是0，第二个数是1，其余的数都是前两个数的和。

显然我们很容易用递归实现，但是会超时的，因为计算第n个位置的斐波那契数的大小时，会重复很多次的计算某些位置的斐波那契数，因此如果我们能记录下已经计算过的位置对应的斐波那契数时，当再次需要该位置的斐波那契数时，就不用再重复的进行计算了。

代码

class Solution {long long memo[101];
public:int fib(int n) {memset(memo,-1,sizeof memo);// std::fill(memo, memo + 101, -1);return dfs(n);}int dfs(int n){if(memo[n]!=-1)return memo[n];if(n==0 || n==1){memo[n]=n;return memo[n];}memo[n]=(dfs(n-1)+dfs(n-2))%1000000007;return memo[n];}
};class Solution {
// public:
//     int fib(int n) {
//         if(n==0 || n==1)
//             return n;
//         vector<int> dp(n+1);
//         dp[0]=0,dp[1]=1;
//         for(int i=2;i<=n;i++)
//             dp[i]=(dp[i-1]+dp[i-2])%1000000007;
//         return dp[n];
//     }
// };

不同路径

题目

思路

本道题很容易使用递归实现，但是会超时，原因同上一道题一样，会大量重复的计算一些以某些位置为起点到终点的路径数，而且时间复杂度是呈指数级别的，因此，我们可以和上一道题一样，如果将已经计算过的以某些位置为起点到终点的路径数记录下来，当再次求以这些位置为起点到终点的路径数时，直接使用即可，避免了大量的重复计算。

代码

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 x,int y,vector<vector<int>>& memo){if(memo[x][y]!=0) return memo[x][y];if(x==0|| y==0) return 0;if(x==1 && y==1){memo[x][y]=1;return 1;}else{memo[x][y]=dfs(x-1,y,memo)+dfs(x,y-1,memo);return memo[x][y];}}
};class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));// dp[0][1]=1;dp[1][0]=1;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m][n];}
};

最长递增子序列

题目

思路

这道题已经在之前的博客中写过了，之前使用的是动态规划和贪心+二分，之前的动态规划是从前往后分析的，下面将使用递归+记忆化搜素，以及从后往前的分析的动态规划。

递归+记忆化搜素

从头到尾扫描数组，分别计算以该位置为起点的最长递增子序列的长度，并把每次计算好的结果进行记录，当下次再次用到以已记录位置为起点的最长递增子序列的长度时，直接拿已经计算好的结果即可，避免了不少重复的计算。

从后往前的分析的动态规划

可以说是在分析前面的递归+记忆化搜素方法的基础上摸索出来的，如何定义状态表示和状态转移方程等，这里不再赘述，可以参考之前的博客。

代码

class Solution {
public:int lengthOfLIS(vector<int>& nums) {//记忆化搜索int ret=1;vector<int> memo(nums.size());for(int i=0;i<nums.size();i++)ret=max(ret,dfs(i,nums,memo));return ret;}int dfs(int pos,vector<int>& nums,vector<int>& memo){if(memo[pos]!=0) return memo[pos];int k=1;for(int i=pos+1;i<nums.size();i++)if(nums[i]>nums[pos])k=max(k,dfs(i,nums,memo)+1);memo[pos]=k;return k;}
};//递归+记忆化搜素 class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();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);}return *max_element(dp.begin(),dp.end());}
};//动态规划

猜数字大小II

题目

思路

上面之所以没有截示例，是因为示例比较长，而且文字描述很多，比较容易看晕，下面也是采用递归+记忆化搜素来解决，因为如果只使用递归会超时，因为会大量的重复计算相同位置的值，如果能够将每次计算好的值保存起来，下次使用时直接取，就能够较少大量的操作，更佳。

从头到尾扫描整个数组，分别计算以该位置为起点的最大花费，然后计算所有起始位置的最大花费的最小值。

代码

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

矩阵中的最长递增路径

题目

思路

下面也是采用递归+记忆化搜素来解决，因为如果只使用递归会超时，因为会大量重复计算以某位置为起点的最长递增路径，如果能够记录下以某位置为起点的最长递增路径，当下次使用时直接取即可，就能够减少大量的重复计算，以示例1为例，比如就以【2】【1】位置的1为起始位置，计算时会有一条向上到6的路径，但是如果已经计算过以这个6为起始位置的最长递增路径的长度，可以直接使用，就不用再重复计算了。

代码

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