记忆化搜索的介绍-平芜编程栈

1.斐波那契数

509. 斐波那契数 - 力扣（LeetCode）https://leetcode.cn/problems/fibonacci-number/description/(通过这道题来理解记忆化搜索)这道题解法一是递归，dfs使命是给个数n，返回第n个斐波那契数。第n个斐波那契数是前一个和前两个加起来就行，递归出口是n==0或n==1时值就是n：

接下来分析一下这个递归，比如n等于5，主函数那调dfs(5)，递归函数中求d(5)展为d(4)和d(3)，求d(4)时展为d(3)和d(2)，同理求d(3)时会去求d(2)和d(1)；在求下面d(3)和d(3)时同理会展....：

时间复杂度近似是O(2^n)。这个递归算法为何非常慢？因为我们会重复的计算一些问题，比如：

这两个d(3)展开的子树一模一样，它们向上返回的时候值肯定是一样的。能否这样优化？此时来个大表我们称为备忘录，把d(3)返回x的信息放进备忘录：

当下一次重新进入右边d(3)的时候，就再不展开了，直接从备忘录中拿出X返回：

像这样的一种优化方式我们称为记忆化搜索，也就是当我们在递归过程中，有一些完全相同的问题时，我们可把完全相同的问题的结果塞备忘录中，再遇到相同问题时直接从备忘录中拿值就行(带备忘录的递归)。这样下来时间复杂度变成O(N)了：

那如何实现记忆化搜索？1.添加一个备忘录。2.递归每次返回的时候将结果放到备忘录里面。3.在每次进入递归的时候，往备忘录里面瞅一瞅。其中备忘录方式是先找可变参数，把可变参数和返回值的映射关系存起来，该题可用数组。初始化备忘录时初始化为dfs中永远不出现的一个值返回，这样确保开始看备忘录时没有值，也可防止冲突下面实现。下面来实现：

2.不同路径

62. 不同路径 - 力扣（LeetCode）https://leetcode.cn/problems/unique-paths/description/先想想如何用暴搜(递归)解决，然后把暴搜代码改为记忆化搜索(不是所有暴搜都能改成记忆化搜索，而是递归中发现遇到大量重复问题时我们才能用记忆化搜索解决)。递归：

dfs两个参数是i和j，直接返回1 1到i j有多少种方法。现在设计函数体：

假设三角是个位置，想求1 1到三角有多少种方式。只关心两个圈的位置：

因为知道到达圈有多少种方式，到三角的方式也就自然知道了：

1.因为每次考虑上边和左边，i==0或j==0到不了，所以返回0。2.i等于1且j等于1时没左和上，只有1种方式：

接下来看看能否把暴搜转化为记忆化搜索，如调dfs(4,4)：

有重复。因此1.搞个备忘录。2.递归前查备忘录。3.返回前把结果存备忘录中。这里备忘录是二维，因为有两个可变参数，规模是int[m+1][n+1]，因为保证访问到m和n。下面来实现：

3.最长递增序列

300. 最长递增子序列 - 力扣（LeetCode）https://leetcode.cn/problems/longest-increasing-subsequence/description/1.递归，如[2,5,3,7,101,18]，如果我们可以暴力的把所有递增子序列找到，然后找出其中最长的那个就可以了。开始后暴力枚举所有的起点：

接下来从原始基础上往后面添加元素，只能从后面元素开始考虑：

接下来从第二个数后面数中考虑第三个数：

下面设计递归：每一次想找到以这个位置为起点的最长递增子序列的长度，所以dfs可这样设计，int dfs(pos)，传一个pos，返回以这个位置为起点最长递增子序列的长度。函数体是i从pos+1位置开始一直到n，找到从这些位置开始的递增子序列的最大值，最后加1。不用出口，因为到n循环就结束了。改为记忆化搜索，还是老三样。下面来实现(ret=1，否则pos最后一个位置时for进不去，最后返回了0)：

4.猜数字大小II

375. 猜数字大小 II - 力扣（LeetCode）https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/下面理解一下：比如从1~10中猜一个数，最终目标是10，但我不知道我可能先选5。因为确保获胜，挑完5后如果猜大了我以二分思想选2，猜小了我选7。2或7的基础上继续选：

这样是分支可能出现的策略。用这样的策略必须保证准备这么多钱才行：

一般猜会有很多策略：

这里最左边策略最小。我们玩这个游戏会有特别多的策略，我们要找出花钱最少的策略，暴力枚举所有策略，如何解决？现在n==10，开始后我要从[1,10]中随意选个数i作为头节点，如果选大了接下来从[1~ i-1]选个点作为头节点，若选小了去[i+1,10]选这个数做头节点：

我在处理左边区间时依旧选个数，然后继续去处理左右区间，右区间也一样：

这里出现了重复情况：你给我一个区间，我随便选个头，然后处理一下左子树，处理一下右子树，所有头中向上返回一个最小值：

此时左右都向上传了一个值：

i拿到x y后要的是最大值。因为根处理的以根为基础的所有情况，为了确保赢必须是最大值，然后然后再加上当前选的位置。int dfs(1,10)，dfs设计时告诉一个区间，然后返回int，表示这个区间中能保证胜利的最小值。函数体里从1~10枚举头节点，然后dfs一下头节点的左右区间，选中最大值加i，然后把所有情况最小值向上返回。它可以改记忆化：

选不同节点分散下去涉及了相同的情况。下面实现(不存在区间返回0，到叶子节点肯定可猜中不用花钱)：