记忆化搜索专题篇

目录

斐波那契数

不同路径

最长递增子序列

猜数字大小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;
    }
};