系统学习算法：专题十二 记忆化搜索

什么是记忆化搜索，我们先用一道经典例题来引入，斐波那契数

题目一：

相信一开始学编程语言的时候，就一定碰到过这道题，在学循环的时候，我们就用for循环来解决，然后学到了递归，我们又用递归来解决，因此我们大概率第一反应是用递归

代码（递归）：

class Solution {
    public int fib(int n) {
        //递归结束条件
        if(n==0||n==1){
            return n;
        }
        //递归公式
        return fib(n-1)+fib(n-2);
    }
}

虽然通过了，但是运行时间却很落后了

因此我们要分析时间复杂度

 以n=5时，画出递归展开图

可以发现每次都是以二叉树展开，那么时间复杂度就是O（2^N），是指数级别

指数级别当然不算很好的时间复杂度，可能看n=5时觉得还好，但是一旦超过一定值，那么就会发生指数爆炸，那么消耗时间增长幅度就很恐怖了

因此我们要分析一下能不能优化，很容易发现，其中有很多重复的操作，一开始左分支就求过d（3）了，右分支又要求一遍d（3），求了2次d（3），同理，d（2）也重复求了3次，那么就知道了为什么消耗时间会很高，因为有大部分的时间都在干重复的事情，而这个事情重复干没有意义，完全可以进行优化

那么我们的想法当然是搞一个“备忘录”，这样子我们干完一件事，把结果放进备忘录里，每次干之前都去备忘录里看看，有没有结果能直接用，没有那就说明之前没干过，这是第一次干，那么只能老老实实去干，如果干过了那么直接就抄结果就好了，就好比数学公式，能记住公式结果直接用就好了，不能每次都从头推导吧，太浪费时间了

那么这个备忘录要怎么实现呢，要根据题目的可变参数和返回类型来创建，不同题目实现的备忘录也不同，像我们这道题，可变参数是第n个斐波那契数，n是整型，而这个数的返回值也是整型，所以这个备忘录的映射关系就是<int,int>，那么就可以用数组或哈希表来作为备忘录

这道题数据范围不大，0—30，用数组就足够了

因此我们就用数组作为备忘录，而备忘录一开始要初始化，初始化的时候要记住，必须是返回值之外的数，像斐波那契数一定大于等于0，那么我们就初始化为-1，这样我们遇见-1就知道这是没干过的，如果初始化为0，那么遇见0就有两种可能，返回值就为0或者没干过的，就不确定了

代码（记忆化搜索）：

class Solution {
    int[] memo=new int[31];
    //初始化
    public void begin(int[] memo){
        for(int i=0;i<memo.length;i++){
            memo[i]=-1;
        }
    }
    public 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];
    }
    public int fib(int n) {
        begin(memo);
        return dfs(n);
    }
}

时间直接来到0ms，分析一下时间复杂度，因为只需要计算一次第0个到第n个斐波那契数列，剩下直接查找拿结果就是了，查找的时间复杂度是常数级，忽略不计，所以时间复杂度为O（N），来到线性级复杂度，已经很优秀了

而还有一种解法，就是动态规划，而动态规划和记忆化搜索很像

完全只是换了一种方式，但思路都是一样的，即将已经计算过的值存起来

代码（动态规划）：

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

时间复杂度也是O（N）

但这道题的最优解其实是矩阵快速幂，其时间复杂度为O（logN），但主要用这道题来引入记忆化搜索，就不扩展了

到此，对记忆化搜索有了一定理解了，那就是带记忆的去dfs

题目二：

思路：

题意很简单， 就是机器人只能向右和下移动，问有多少条路可以从左上角到达右下角

先用暴搜的方法来写的话，应该没什么难度

我们假设dfs的功能是返回到这个格子有多少种路径，又因为只能向右和向下，所以到达当前格子的路径等于当前位置的左边格子和当前位置的上边格子的路径之和

所以递归公式就找到了：dfs（i，j）= dfs（i-1，j）+ dfs（i，j-1）

而结束条件就是为起点的时候，路径只有一条，而边界情况，越界的不可能有路径，所以返回0

代码（暴搜）：

class Solution {
    public int uniquePaths(int m, int n) {
        //返回到（m-1，n-1）这个点的路径数
        return dfs(m-1,n-1);
    }
    public int dfs(int i,int j){
        //起点
        if(i==0&&j==0){
            return 1;
        }
        //越界
        if(i==-1||j==-1){
            return 0;
        }
        //递归公式
        return dfs(i-1,j)+dfs(i,j-1);
    }
}

结果会超时，分析递归展开图，以（4，4）这个点为例

 可以看到这里就出现了重复的步骤，所以要采用记忆化搜索

还是先搞备忘录，初始化为-1，起点记录1，接下来就是进去先看看是否合法，合法再查找备忘录，有就拿，没有就运算再添加

代码（记忆化搜索）：

class Solution {
    int row,col;
    //备忘录
    int[][] memo;
    public int dfs(int i,int j){
        //起点
        if(i==0&&j==0){
            memo[i][j]=1;
            return 1;
        }
        //越界        
        if(i==-1||j==-1){
            return 0;
        }
        //查备忘录
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        //添加到备忘录
        memo[i][j]=dfs(i-1,j)+dfs(i,j-1);
        //返回结果
        return memo[i][j];
    }
    public int uniquePaths(int m, int n) {
        memo=new int[m][n];
        //初始化
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                memo[i][j]=-1;
            }
        }
        return dfs(m-1,n-1);
    }
}

当然也可以转为动态规划

代码（动态规划）：

class Solution {
    public int uniquePaths(int m, int n) {
        //多一行和一列就不用考虑越界了
        int[][] dp = new int[m + 1][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;
                }
                //越界的默认为0
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }            
        }
        return dp[m][n];
    }
}

题目三：

思路：

先理解题意，子序列就两个特点

第一：简单来说就是原数组的子集，即子序列里面的元素个数小于等于原数组的元素个数，并且元素都来自原数组

第二：与原数组的前后顺序是一样的，比如示例1中，2在101前面，那么只要子序列出现2和101，那么2必须在101之前，101必须在2之后

而题目要求的是最长递增子序列，那么先理解递增，比如示例1中，[10，9]是子序列，但是不是递增的，所以不满足条件；在所有递增的子序列中还要求最长的，那么经过列举就知道长度为4，但注意题目虽说[2，3，7，101]是最长递增子序列，但不唯一，因为同理[2，5，7，18]也是，也就是说3和5可以进行互换，101可以和18互换，两两匹对有四个最长递增子序列，但长度都为4

题意理解好了，就来解决问题

要求最长递增子序列，那么我们就枚举出所有递增子序列，再求最长的

先画决策树

 先选子序列的第一位，如决策树的第一层，然后再选子序列的第二位，如决策树的第二层，如此类推（因为要的是递增，所以不是递增的就剪枝掉了）

 所以这时就开始定义dfs的功能，根据题意要求即给dfs一个原数组的位置，要dfs返回以该位置为起点的最长递增子序列

这里其实比较抽象，画递归展开图很绕，所以就像我们之前专题说的，无条件相信dfs，它一定能实现的，宏观的来看递归

然后编写dfs，其中我们拿到起点位置，那么我们要先遍历所有后面的元素，又因为要递增，所以只有大于当前位置的元素才能用，然后用dfs拿到这个后面的元素的最长递增子序列，此时加上当前元素的长度1，与保存结果进行比较，选出最大的并更新

而结束条件这道题其实没有，因为我们在遍历后面元素时，最后会来到最后元素，而最后元素后面没有元素，就不会进入循环，也就不会进入dfs了，这时就直接返回了，而因为最后元素自己也有长度1，所以要返回1，因此结果要初始化为1，而不是0

主函数则遍历数组，看看以哪个位置为起点的递增子序列最长，然后返回最长的长度

代码（暴力）：

class Solution {
    int ret;
    public int dfs(int[] nums,int cur){
        //初始化为1，因为最后一个元素时，不进循环，且长度为自身1
        int ans=1;
        //遍历后面的元素
        for(int i=cur+1;i<nums.length;i++){
            //如果是递增的
            if(nums[i]>nums[cur]){
                //选出该元素为起点的最长递增子序列加上当前长度和结果的最大值
                ans=Math.max(dfs(nums,i)+1,ans);                    
            }
        }
        return ans;
    }
    public int lengthOfLIS(int[] nums) {
        //遍历数组，看看以哪个为起点的递增子序列最长
        for(int i=0;i<nums.length;i++){
            ret=Math.max(ret,dfs(nums,i));
        }
        //返回最长的
        return ret;
    }
}

结果当然是超时了，这个更恐怖，以前还是二叉树为O（2^N），这道直接多叉树，直接是O（N^N）的时间复杂度了

这时就来想想优化

还是刚刚的决策树，多看一下就发现里面有很多重复计算，比如在2这个分支的时候，我们就算过以5为起点的递增子序列的最长长度，而决策树的第一层后面又来了5，又要重新算，所以我们就可以使用记忆化搜索，添加个备忘录

很简单，就进入dfs的时候，看一下备忘录，有就直接用，没有就老实算，算完了就保存到备忘录，再返回

代码（记忆化搜索）：

class Solution {
    int ret;
    int[] memo;
    public int dfs(int[] nums,int cur){
        //如果备忘录里有
        if(memo[cur]!=0){
            return memo[cur];
        }
        //初始化为1，因为最后一个元素时，不进循环，且长度为自身1
        int ans=1;
        //遍历后面的元素
        for(int i=cur+1;i<nums.length;i++){
            //如果是递增的
            if(nums[i]>nums[cur]){
                //选出该元素为起点的最长递增子序列加上当前长度和结果的最大值
                ans=Math.max(dfs(nums,i)+1,ans);                    
            }
        }
        //添加到备忘录
        memo[cur]=ans;
        return ans;
    }
    public int lengthOfLIS(int[] nums) {
        memo=new int[nums.length];
        //遍历数组，看看以哪个为起点的递增子序列最长
        for(int i=0;i<nums.length;i++){
            ret=Math.max(ret,dfs(nums,i));
        }
        //返回最长的
        return ret;
    }
}

然后随便改成动态规划，因为我们决策树是先从下往上返回的，所以动态规划填表的顺序是从后往前来填的，因为要知道后面的，才能知道前面的

最后一个元素填表时，对应的是长度是自己，所以为1，那么dp表就全部初始化为1，对应记忆化搜索的代码就是ans=1

代码（动态规划）：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int ret=0;
        int[] dp=new int[nums.length];
        //初始化
        Arrays.fill(dp,1);
        //从后往前填
        for(int i=nums.length-1;i>=0;i--){
            //往后找子序列
            for(int j=i+1;j<nums.length;j++){
                //递增
                if(nums[i]<nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            //更新最长的长度
            ret=Math.max(ret,dp[i]);
        }
        return ret;
    }
}

题目四：

思路：

 题意需要看懂，如果看不懂题就根本做不了了，题目会给你一个数，让你返回1—n之间猜数字所花费最少的钱且保证绝对能猜对，而其中会出现不花钱的情况，一种是猜对了，另一种是没必要猜因为答案就剩这一个了，其实本质是一样的

其中的决策树的画法我们可以采用暴力枚举，将所有可能的决策全部枚举出来，且枚举的都是最坏情况，即最后一次才能猜出来

第一层就代表第一次选择猜哪一个数，范围从1—n

第二层就代表第二次选择猜哪一个数，假如上一层选择了k，小于则是1（left）—k-1（right），大于则是k+1（left）—n（right）

如此类推枚举

有非常多的决策情况，但会有一种是最优决策，比如1—10，最优决策就是示例1演示的

所以我们暴力枚举出来就行

而有两种结束情况，在小于区间时，k==left+1时，此时k-1==left，就不用继续了，包能猜对的，直接返回花费0元，而在大于区间时，k==right或者right-1时，此时k+1>=right，也不需要花钱，返回0元即可

代码（暴力）：

class Solution {
    public int getMoneyAmount(int n) {
        //给一个区间，返回所需要的最少钱
        return dfs(1,n);
    }
    public int dfs(int left,int right){
        //如果只剩下一个或者没有右区间了
        if(left>=right){
            return 0;
        }
        int ret=Integer.MAX_VALUE;
        //在left和right区间选猜哪个数需要花ret最少
        for(int i=left;i<=right;i++){
            //小于区间
            int x=dfs(left,i-1);
            //大于区间
            int y=dfs(i+1,right);
            //所有猜的数最少，而每个最少由左右区间最大的决定
            ret=Math.min(Math.max(x,y)+i,ret);
        }
        return ret;
    }
}

这里主要理解一下max和min这里，max用于决定猜的当前这个数最少需要花多少钱，min用于决定猜哪一个数花费最少

当然会超时，所以用记忆化搜索，因为会有重复的计算，比如下面这个例子

[6，10]这个区间就会重复计算，所以每次计算完一个区间，就记录该区间最少需要花多少钱

每次进去的时候就先去备忘录找一下，有就直接用，没有就算一遍，然后存到备忘录里面

因为有两个参数，所以备忘录也应该是二维的

代码（记忆化搜索）：

class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo=new int[n+1][n+1];
        //给一个区间，返回所需要的最少钱
        return dfs(1,n);
    }
    public int dfs(int left,int right){
        //如果只剩下一个或者没有右区间了
        if(left>=right){
            return 0;
        }
        //查看备忘录
        if(memo[left][right]!=0){
            return memo[left][right];
        }
        int ret=Integer.MAX_VALUE;
        //在left和right区间选猜哪个数需要花ret最少
        for(int i=left;i<=right;i++){
            //小于区间
            int x=dfs(left,i-1);
            //大于区间
            int y=dfs(i+1,right);
            //所有猜的数最少，而每个最少由左右区间最大的决定
            ret=Math.min(Math.max(x,y)+i,ret);
        }
        //存进备忘录
        memo[left][right]=ret;
        return ret;
    }
}

题目五：

 思路：

跟之前走迷宫的题几乎一模一样，暴力枚举每一个点的递增路径，选最长的那个

dfs可以有返回值也可以没有返回值

那我们就暴力的时候用没有返回值的，记忆化搜索就用有返回值的，两个版本都看得到

代码（暴力+无返回值dfs）：

class Solution {
    //方向向量数组
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    int row,col,ret;
    public int longestIncreasingPath(int[][] matrix) {
        //行列
        row=matrix.length;
        col=matrix[0].length;
        //暴力遍历每个点的路径情况
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                dfs(matrix,i,j,1);
            }
        }
        //返回最长的递增路径
        return ret;
    }
    public void dfs(int[][] matrix,int i,int j,int count){
        //更新最长路径
        if(count>ret){
            ret=count;
        }
        //上下左右
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            //不越界
            if(x>=0&&x<row&&y>=0&&y<col){
                //递增
                if(matrix[i][j]<matrix[x][y]){
                    //继续遍历下一个点
                    dfs(matrix,x,y,count+1);
                }
            }
        }
    }
}

最后还是超时了，同理可以记录每一个点的最长路径，这样再次经过这个点的时候，就可以直接用了，而不需要再重复计算一次

还是老规矩，先进去看看备忘录有没有，有就用，没有就算一次，然后存进备忘录里

代码（记忆化搜索）：

class Solution {
    //方向向量数组
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    int row,col,ret;
    int[][] memo;
    public int longestIncreasingPath(int[][] matrix) {
        //行列
        row=matrix.length;
        col=matrix[0].length;
        memo=new int[row][col];
        //暴力遍历每个点的路径情况
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ret=Math.max(dfs(matrix,i,j),ret);
            }
        }
        //返回最长的递增路径
        return ret;
    }
    public int dfs(int[][] matrix,int i,int j){
        //查看一下备忘录
        if(memo[i][j]!=0){
            return memo[i][j];
        }
        //算上当前位置路径长度为1
        int count=1;
        //上下左右
        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            //不越界
            if(x>=0&&x<row&&y>=0&&y<col){
                //递增
                if(matrix[i][j]<matrix[x][y]){
                    //找到最长路径的方向
                    count=Math.max(dfs(matrix,x,y)+1,count);
                }
            }
        }
        //记录到备忘录
        memo[i][j]=count;
        //返回该点的最长路径
        return count;
    }
}

总结：

其实难的不是记忆化搜索，而是如何写出暴搜的代码，也就是dfs，如果暴搜能过就过，过不了就看看能不能用记忆化搜索来优化，不是所有的暴搜都能转记忆化搜索的，要看是否存在相同的计算，如果有，那么就添加一个备忘录，dfs进去的时候就看一看备忘录，有就用，没有就算一次，然后再保存到备忘录，几乎是个模板，难的还是dfs

综上所有递归回溯的部分就基本学完了，接下来会继续学其他的算法