【算法】记忆化搜索

概念

在这里插入图片描述

举例

拿斐波那契数列举例
在这里插入图片描述
可以发现一般的求解过程中，有很多重复的子问题，递归的本质就是深度优先遍历，如果此时我们可以记录下此时的值然后记录在哈希表中，下一次递归前先去哈希表中查找如果有该值的答案直接返回即可。
在这里插入图片描述
这样完全二叉树就可以转为单链结构

应用

leetcode397.整数替换

给定一个正整数 n ，你可以做如下操作：

如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的最小替换次数。

示例 1：

输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1
示例 2：

输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1

class Solution {
public:
    unordered_map<int,int> hash;
    int integerReplacement(int n) {
        if(n==1)
            return 0;
        int ans=0;
        if(hash.count(n))
            return hash[n];
        if(n%2==0)
        {
            ans=integerReplacement(n/2)+1;
        }
        else
        {
            ans=min(integerReplacement(n/2+1)+1,integerReplacement(n-1))+1;
        }
        hash[n]=ans;
        return ans;
    }
};

leetcode647.回文子串

给你一个字符串 s ，请你统计并返回这个字符串中回文子串的数目。

回文字符串是正着读和倒过来读一样的字符串。

子字符串是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

class Solution {
    int dp[1000][1000];

    int dfs(const string& s,int l,int r)
    {
        if(l>r)
            return 1;
        if(dp[l][r]!=-1)
            return dp[l][r];//记忆化搜索
        if(s[l]==s[r])
            dp[l][r]=dfs(s,l+1,r-1);
        else
            dp[l][r]=0;

        return dp[l][r];
    }
public:
    int countSubstrings(string s) {
        int n=s.size();
        memset(dp,-1,sizeof(dp));
        int ans=0;
        
        for(int i=0;i<n;i++)
            dp[i][i]=1,ans++;

        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(dp[i][j]==-1)
                {
                    dp[i][j]=dfs(s,i,j);
                }
                if(dp[i][j]==1)
                    ++ans;
            }
            
        }

        return ans;
    }
};

思路：这里我们用ans记录回文子序列的个数，dp[i][j]表示从i位置到j位置是否为回文子序列，当i=j即单个元素是回文串，然后两层循环遍历每一个子序列，状态转移方程：dp[i][j]=s[i]==s[j] and dp[i+1][j-1],这里可以采用记忆化搜索的方式，定义一个dfs函数，记录从开头到结尾的子序列是否是回文的。

lcr112.矩阵中的最长递增路径（hard）

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：
在这里插入图片描述

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
在这里插入图片描述

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

class Solution {
    int dp[200][200];
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    int dfs(vector<vector<int>> & matrix,int m,int n,int i,int j)
    {
        if(dp[i][j]!=-1)
            return dp[i][j];
        int len=1;
        for(int a=0;a<4;a++)
        {
            int x=i+dx[a],y=j+dy[a];
            if(x<0||y<0||x>m-1||y>n-1)
                continue;
            if(matrix[x][y]<=matrix[i][j])
                continue;
            len=max(len,dfs(matrix,m,n,x,y)+1);
        }
        dp[i][j]=len;
        return len;
    }

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        memset(dp,-1,sizeof dp);
        int m=matrix.size();
        int n=matrix[0].size();
        int len=1;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                len=max(len,dfs(matrix,m,n,i,j));
            }
        }

        return len;
    }
};