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

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])；

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

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

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）

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）

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算法，要求分块的面积或者分块的个数，所以还是要好好进行区分总结！！！

希望对你也有帮助~