递归、搜索与回溯算法（专题六：记忆化搜索）

目录1. 什么是记忆化搜索例子斐波那契数1.1 解法一递归1.2 解法二记忆化搜索1.2.1 记忆化搜索比递归多了什么1.2.2 提出一个问题什么时候要使用记忆化搜索呢1.3 解法三动态规划1.3.1 先复习一下动态规划的核心步骤5个并将动态规划的每一步对应记忆化搜索加强版的递归的每一步1.3.2 通过上面的解析发现一个特点1.3.3 动态规划 and 记忆化搜索的本质补充2. 题目2.1 不同路径medium2.1.1 递归解法2.1.2 记忆化搜索解法2.1.3 动态规划解法2.2 最长递增子序列2.2.1 递归解法2.2.2 记忆化搜索解法2.2.3 动态规划解法2.3 猜数字大小 Ⅱ2.3.1 递归解法2.3.2 记忆化搜索解法2.4 矩阵中的最长递增路径2.4.1 递归解法2.4.2 记忆化搜索解法1. 什么是记忆化搜索例子斐波那契数力扣题目链接记过前面几篇文章中我介绍了什么递归、搜索和回溯以及他们之间的关系。接下来我们进阶一下来一起看看什么是记忆化搜索看看记忆化搜索与递归乃至动态规划算法之间有什么联系吧。我打算用一道很经典的例题分享一下什么是记忆化搜索这道题就是斐波那契数斐波那契数的解法有很多①循环②递归③动态规划④记忆化搜索⑤矩阵快速幂在这几种解法中矩阵快速幂的时间复杂度是最小的。关于矩阵快速幂我会在接下来的文章中分享给大家敬请期待题目如下解法分析1.1 解法一递归​递归解决这题会出现的问题① 进行了很多重复性的计算例如fib(3)、fib(2)都计算了多次这就大大增加运算时间时间复杂度为O(2^n)。② 如果 n 太大fib(n)的执行可能还会导致栈溢出。//第一种方法递归 public int fib1(int n) { if(n 0) return 0; if(n 1) return 1; return fib(n - 1) fib(n - 2); }​我们可以发现递归是可以执行通过的。这道题给的测试用例都是比较少所以不会导致超时的现象。1.2 解法二记忆化搜索1.2.1 记忆化搜索比递归多了什么答比递归多了一个“备忘录”的功能加强版的递归。在上面的第一种解法有提到递归的缺点就是有事会进行大量的重复计算导致时间复杂度过大。“备忘录”就是用来存储每次递归的结果如果在另一个分支中有进行一样的运算就不需要再进行递归展开了只要从“备忘录”中将值取出来直接返回即可。具体看下图首先我们创建一个备忘录例如int memo[n];​如何实现记忆化搜索① 添加一个备忘录。② 递归每次返回时将结果放到备忘录里面。③ 在每次进入递归之前先往备忘录里瞅一瞅看看是否已经存在了 。int[] memo;//作为备忘录 //第二种方法记忆化搜索 public int fib(int n) { //初始化 memo new int[n 1]; Arrays.fill(memo, -1); //进行记忆化深搜 return dfs(n); } int dfs(int n){ if(memo[n] ! -1) return memo[n]; if(n 1){ memo[n] n; return n; } memo[n] dfs(n - 1) dfs(n - 2); return memo[n]; }​发现了一个有趣的结果使用递归解这道题花了10ms而使用记忆化搜索只要0ms虽然力扣的执行时间不是很严谨但也可以一看记忆化搜索省略了很多重复计算的步骤所以时间复杂度大大减少了为 O(n)。1.2.2 提出一个问题什么时候要使用记忆化搜索呢答① 只有当一个道题有许多重复计算换句话说有许多重复的子问题时可以使用记忆化搜索来降低时间复杂度。② 如果没有许多重复计算换句话说递归展开图只是一棵单分支树就没必要用记忆化搜索了。1.3 解法三动态规划1.3.1 先复习一下动态规划的核心步骤5个并将动态规划的每一步对应记忆化搜索加强版的递归的每一步① 确定动态表示dp[i]要表示什么dp[i]表示第i位的斐波那契数——递归dfs函数的含义函数头有什么参数、什么返回值② 确定动态转移方程dp[i] dp[i - 1] dp[i - 2]——递归dfs函数的主体函数做了什么③ 初始化防止越界dp[0] 0dp[1] 1——递归dfs函数的递归出口n 0 或 n 1时④ 确定填表顺序从左往右——递归填写备忘录的顺序⑤ 确定返回值dp[n]——递归主函数如何调用dfs函数int[] dp; public int fib(int n) { //1.对dp初始化 dp new int[n 1]; dp[0] 0; if(n 0) dp[1] 1; //2.开始填表 for(int i 2;i n;i){ dp[i] dp[i - 1] dp[i - 2]; } //3.返回值 return dp[n]; }​1.3.2 通过上面的解析发现一个特点记忆化搜索是进行自顶向下计算动态规划是进行自底向上计算。​1.3.3 动态规划 and 记忆化搜索的本质① 都是暴力解法一一枚举② 都是将计算好的结果存储起来③ 记忆化搜索递归的形式动态规划递推的形式利用循环补充1带备忘录的递归 vs 带备忘录的动态规划 vs 记忆化搜索 三者都是一回事就是记忆化搜索或者说动态规划。2能用暴搜解的题一般可以改成记忆化搜索但不一定可以改成动态规划。暴搜的本质是给动态规划提供一个“填表方向”。经过上面的分享大家应该对递归、记忆化搜索和动态规划有了一个新的了解接下来通过做题来巩固加深我们的知识体系吧。2. 题目2.1 不同路径medium力扣题目链接解析2.1.1 递归解法​//第一种递归解法 public int uniquePaths(int m, int n) { if(m 0 || n 0) return 0; if(m 1 n 1) return 1; return uniquePaths(m - 1, n) uniquePaths(m, n - 1); }​在运行的时候是可以运行通过但是当 m 和 n 太大了呢我们来看看提交会发生什么。​超时m和n一大就发什么超时现象接下来看看用记忆化搜索又怎么样。2.1.2 记忆化搜索解法​//第二种记忆化搜索 public int uniquePaths(int m, int n) { int[][] memo new int[m 1][n 1]; return dfs(m,n,memo); } int dfs(int m,int n,int[][] memo) { if(m 0 || n 0) return 0; if(memo[m][n] ! 0) return memo[m][n]; if(m 1 n 1){ memo[m][n] 1; return 1; } memo[m][n] dfs(m-1,n,memo) dfs(m,n-1,memo); return memo[m][n]; }​此时提交就可以通过了不会发生超时。2.1.3 动态规划解法1确定动态表示dp[i][j] 为 到当前位置有多少种路径。2状态转移方程dp[i][j] dp[i - 1][j] dp[i][j - 1]。3初始化dp[0][j] dp[i][0] 0dp[1][1] 1。4填表顺序从左往右从上往下。5返回值return dp[m][n]。// 第三种动态规划解法 public int uniquePaths(int m, int n) { //1.创建dp表 int[][] dp new int[m 1][n 1]; //2和3一起初始化和填表 dp[1][1] 1; for(int i 1;i m 1;i){ for(int j 1;j n 1;j){ if(i 1 j 1) continue;//到(1,1)位置的路径都是1不用再修改了 dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } //4.返回值 return dp[m][n]; }​2.2 最长递增子序列力扣题目链接解析2.2.1 递归解法public int lengthOfLIS(int[] nums){ int ret 0; for(int i 0;i nums.length;i){ ret Math.max(ret,dfs(nums,i)); } return ret; } public int dfs(int[] nums,int pos){ int ret 1; for(int i pos 1;i nums.length;i){ if(nums[pos] nums[i]) ret Math.max(ret,dfs(nums,i) 1); } return ret; }我们可以发现一些测试用例是可以通过但是当数组的大小过于大时就会报超时的错误对于这种情况可以将代码改成记忆化搜索或者动态规划用空间换取时间减小时间复杂度2.2.2 记忆化搜索解法例如这种情况在pos的第一个分支pos1已经计算过了则在根结点的第二个分支就不需要在此重复计算pos1了。int[] memo; public int lengthOfLIS(int[] nums){ memo new int[nums.length]; int ret 0; for(int i 0;i nums.length;i){ ret Math.max(ret,dfs(nums,i)); } return ret; } public int dfs(int[] nums,int pos){ if(memo[pos] ! 0){ return memo[pos]; } int ret 1; for(int i pos 1;i nums.length;i){ if(nums[pos] nums[i]) ret Math.max(ret,dfs(nums,i) 1); } memo[pos] ret; return ret; }2.2.3 动态规划解法1确定动态表示dp[i] 表示从第i个位置开始符合子序列条件的子序列长度为多少2状态转移方程当后一个元素大于前一个元素有 dp[i] Math.max(dp[i],dp[j] 1);3初始化Arrays.fill(dp,1); 所有的位置都是1最糟糕的情况就是该位置的元素自己所以就是1。4填表顺序从右往左。其实就是从少到多的过程。5返回值ret Math.max(dp[i],ret); 看从哪个位置开始能得到最长的子序列。//第三种动态规划 public int lengthOfLIS(int[] nums) { int[] dp new int[nums.length 1]; int ret 0; 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(dp[i],ret); } return ret; }2.3 猜数字大小 Ⅱ力扣题目链接解析2.3.1 递归解法//第一种方法暴搜 public int getMoneyAmount(int n) { return dfs1(1,n); } int dfs1(int left,int right){ /* 当left right证明已经找到该数所以就不需要支付费用 当1作为根结点则有 [left,head - 1] [1,0]这种情况不存在也 要返回0因为不存在所以不会有消耗 */ if(left right) return 0; int ret Integer.MAX_VALUE; for(int head left;head right;head){ //x是用来找左子树的值 int x dfs1(left,head - 1); //y是用来找右子树的值 int y dfs1(head 1,right); ret Math.min(Math.max(x,y)head,ret); } return ret; }这种超时报错我们在上面的例题中已经遇到了许多次所以我们将代码改为记忆化搜索2.3.2 记忆化搜索解法可以发现在选择5作为根结点时出现了[6, 10]的区间在选择3作为根结点时也出现了[6, 10]的区间这部分就导致了重复计算。所以我们将每个区间的结果保存起来减少时间复杂度。//第二种方法记忆化搜索 int[][] memo; public int getMoneyAmount(int n) { memo new int[n 1][n 1]; 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 Integer.MAX_VALUE; for(int head left;head right;head){ int x dfs(left,head - 1); int y dfs(head 1,right); ret Math.min(Math.max(x,y)head,ret); } memo[left][right] ret; return ret; }2.4 矩阵中的最长递增路径力扣题目链接解析2.4.1 递归解法算法思路暴搜a. 递归含义给 dfs ⼀个使命给他⼀个下标 [i, j] 返回从这个位置开始的最⻓递增路径的⻓度b. 函数体上下左右四个⽅向瞅⼀瞅哪⾥能过去就过去统计四个⽅向上的最⼤⻓度c. 递归出⼝因为我们是先判断再进⼊递归因此没有出⼝~//方向的选择具体看上图 int[] dx {-1,0,1,0}; int[] dy {0,1,0,-1}; int m,n; public int longestIncreasingPath(int[][] matrix) { m matrix.length; n matrix[0].length; int ret 0; for(int i 0;i m;i){ for(int j 0;j n;j){ ret Math.max(ret,dfs(matrix,i,j)); } } return ret; } public int dfs(int[][] matrix,int i,int j){ int ret 1; //从四个方向进行暴搜 for(int k 0;k 4;k){ int x i dx[k],y j dy[k]; if(x 0 x m y 0 y n matrix[x][y] matrix[i][j]){ ret Math.max(ret,dfs(matrix,x,y) 1); } } return ret; }这种超时报错我们在上面的例题中已经遇到了许多次所以我们将代码改为记忆化搜索。2.4.2 记忆化搜索解法注这道题的递归图为什么会重复就不给小伙伴们画了大家可以动手画一画想想为什么会有重复计算int[] dx {-1,0,1,0}; int[] dy {0,1,0,-1}; int[][] memo;//“备忘录” int m,n; public int longestIncreasingPath(int[][] matrix) { m matrix.length; n matrix[0].length; memo new int[m][n]; int ret 0; for(int i 0;i m;i){ for(int j 0;j n;j){ ret Math.max(ret,dfs(matrix,i,j)); } } return ret; } public int dfs(int[][] matrix,int i,int j){ if(memo[i][j] ! 0){ return memo[i][j]; } int ret 1; for(int k 0;k 4;k){ int x i dx[k],y j dy[k]; if(x 0 x m y 0 y n matrix[x][y] matrix[i][j]){ ret Math.max(ret,dfs(matrix,x,y) 1); } } memo[i][j] ret;//每次结果保存到备忘录 return ret; }