记忆化搜索
定义
记忆化搜索（Memoization）是一种优化技术，用于通过存储已经计算过的结果来避免重复计算。它是一种动态规划的实现方式，通常用于递归算法中。通过将中间结果存储在数据结构（如数组或字典）中，记忆化搜索可以显著提高算法的效率，特别是在解决具有重叠子问题的计算问题时。
简单来说就是当算法需要计算某个子问题的结果时，它首先检查是否已经计算过该问题。如果已经计算过，则直接返回已经存储的结果；否则，计算该问题，并将结果存储下来以备将来使用。
记忆化搜索与递推区别
记忆化搜索：
「自顶向下」的解决问题，采用自然的递归方式编写过程，在过程中会保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
优点：代码清晰易懂，可以有效的处理一些复杂的状态转移方程。有些状态转移方程是非常复杂的，使用记忆化搜索可以将复杂的状态转移方程拆分成多个子问题，通过递归调用来解决。
缺点：可能会因为递归深度过大而导致栈溢出问题。
递推：
「自底向上」的解决问题，采用循环的方式编写过程，在过程中通过保存每个子问题的解（通常保存在一个数组或哈希表中）来避免重复计算。
优点：避免了深度过大问题，不存在栈溢出问题。计算顺序比较明确，易于实现。
缺点：无法处理一些复杂的状态转移方程。有些状态转移方程非常复杂，如果使用递推方法来计算，就会导致代码实现变得非常困难。
如何写记忆化搜索
方法1
- 把这道题的 dp 状态和方程写出来
- 根据它们写出 dfs 函数
- 添加记忆化数组
方法2
- 写出这道题的暴搜程序（最好是dfs）
- 将这个 dfs 改成「无需外部变量」的 dfs
- 添加记忆化数组