记忆化搜索到底是不是动态规划？文末有惊喜~

前言

在解算法题时，经常看到很多题解中将动态规划与记忆化搜索并列介绍，那么他们之间到底存在怎样的关系？记忆化搜索的方式到底算不算动态规划？又或者说他们是不是同一种东西呢？下面就让我们一起来探索下吧！

记忆化搜索 vs 狭义动态规划

两者本质上是一样的：

都有重叠子问题，且相比暴力求解，使用这两种方法进行优化的目的是要跳过这些重叠子问题；

都有 base case 和状态转移方程。

区别主要有五点：

记忆化搜索的编程模式是递归，而狭义动态规划的编程模式是递推。一般来说，在相同计算量下，因为需要不断调用函数，递归的开销要比递推更大；

记忆化搜索是自顶向下求解，从目标状态到边界条件；而狭义动态规划是自底向上，从边界条件到目标状态；

记忆化搜索不需要严格设计好计算顺序，备忘录没有记录则进行计算即可；而动态规划必须分析已有的 base case，严格设计 DP table 的递推计算顺序；

记忆化搜索是以使用备忘录避免重复计算来跳过重叠子问题的，而狭义动态规划是以设计巧妙的递推顺序来压根就不产生重叠子问题的。

多个状态下，动态规划通常会生成大量无效的状态，而记忆化搜索则不会，这是记忆化搜索在速度上有可能超越狭义动态规划的地方。

算法分析

1. 传统递归

在记忆化搜索和动态规划之前，我们先来了解下传统递归，首先来看第一个例子，斐波那契数列。

斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……

斐波那契数列以如下被以递推的方法定义：

$\ce{F(1)=1，F(2)=1,F(n)=F(n−1)+F(n−2)（n≥3，n∈N^∗）}$

代码实现如下：

上述代码提交后，会发现到计算到41时，已经超出时间限制，原因在于会重复计算已经出现的值，所以递归的最大缺点就是大量的重复计算，时间复杂度高。

2. 记忆化递归（自顶向下）

在递归过程中会重复计算已经出现的值，那么此时可以建立一个“记忆”数组来储存已经递归出来的值。如果当前值已经在数组中了就直接返回，无需再计算。

原理： 在递归法的基础上，新建一个长度为 n 的数组，用于在递归时存储 f(0) 至 f(n) 的数字值，重复遇到某数字则直接从数组取用，避免了重复的递归计算。

缺点： 记忆化存储需要使用 O(N) 的额外空间。

其实就是以空间换时间，改进代码如下：

3. 动态规划（自底向上）

在记忆化递归中，已经能够解决时间复杂度的问题了，但额外增加了空间，若在此优化空间复杂度使用动态规划即可解决。一般来说，只要递归能够解决的动态规划就一定能够解决，使用动态规划方法实现时间和空间的优化。

代码如下：

总结

两者本质上是一样的，但是编程形式上有所不同。

记忆化搜索使用备忘录记录状态，使用dp()函数进行状态转移；

狭义动态规划使用 DP table 记录状态，使用递推迭代进行状态转移。

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

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

提取码：2cg8