递归 or 记忆化搜索？谁更优秀？文末有惊喜~~

前言

在动态规划中，我们通常使用二维数组来存储子问题的最优解，但是对于某些问题，如果使用二维数组存储所有子问题的解，可能会造成空间复杂度过高。

这个时候我们可以考虑使用**记忆化搜索**来优化空间复杂度。

算法介绍

记忆化搜索实际上是用递归来实现的，但是在递归的过程中有许多结果是被反复计算的，这样会大大降低算法的执行效率。

而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算再次用到时直接取出结果，避免重复运算，因此极大的提高了算法的效率。

举个例子，比如「斐波那契数列」的定义是：f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2)。如果我们使用递归算法求解第 n 个斐波那契数，则对应的递推过程如下图所示：

从图中可以看出：如果使用普通递归算法，想要计算 f(5)，需要先计算 f(3) 和 f(4)，而在计算 f(4) 时还需要计算 f(3)。这样 f(3) 就进行了多次计算，同理 f(0)、f(1)、f(2) 都进行了多次计算，从而导致了重复计算问题。

为了避免重复计算，在递归的同时，我们可以使用一个缓存（数组或哈希表）来保存已经求解过的 f(k) 的结果。如上图所示，当递归调用用到 f(k) 时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。

使用记忆化搜索方法解决斐波那契数列的代码如下：

写在最后

记忆化搜索是一种常见的动态规划优化方法，可以避免重复计算，提高算法效率。在使用记忆化搜索时，我们可以将递归算法与缓存技术结合起来，通过缓存子问题的解来避免重复计算，从而节省时间和空间复杂度。

最后送大家一份 JetBrains IDEA 破解教程和干货，快拿去用吧：

百度网盘链接：https://pan.baidu.com/s/1jxvnKgTsTbkVmjcPGeTm0g

提取码：2cg8