记忆化搜索

动态规划 / memo

本地源文件：docs/dp__memo.md

记忆化搜索

定义

记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式．

因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式．

引入

[[NOIP2005] 采药](https://www.luogu.com.cn/problem/P1048)

山洞里有 𝑀M 株不同的草药，采每一株都需要一些时间 𝑡𝑖ti，每一株也有它自身的价值 𝑣𝑖vi．给你一段时间 𝑇T，在这段时间里，你可以采到一些草药．让采到的草药的总价值最大．

1 ≤𝑇 ≤1031≤T≤103，1 ≤𝑡𝑖,𝑣𝑖,𝑀 ≤1001≤ti,vi,M≤100

朴素的 DFS 做法

很容易实现这样一个朴素的搜索做法：在搜索时记录下当前准备选第几个物品、剩余的时间是多少、已经获得的价值是多少这三个参数，然后枚举当前物品是否被选，转移到相应的状态．

实现

C++Python

---|---

---|---

这种做法的时间复杂度是指数级别的，并不能通过本题．

优化

上面的做法为什么效率低下呢？因为同一个状态会被访问多次．

如果我们每查询完一个状态后将该状态的信息存储下来，再次需要访问这个状态就可以直接使用之前计算得到的信息，从而避免重复计算．这充分利用了动态规划中很多问题具有大量重叠子问题的特点，属于用空间换时间的「记忆化」思想．

具体到本题上，我们在朴素的 DFS 的基础上，增加一个数组 mem 来记录每个 dfs(pos,tleft) 的返回值．刚开始把 mem 中每个值都设成 -1（代表没求解过）．每次需要访问一个状态时，如果相应状态的值在 mem 中为 -1，则递归访问该状态．否则我们直接使用 mem 中已经存储过的值即可．

通过这样的处理，我们确保了每个状态只会被访问一次，因此该算法的时间复杂度为 𝑂(𝑇𝑀)O(TM)．

实现

C++Python

---|---

---|---

与递推的联系与区别

在求解动态规划的问题时，记忆化搜索与递推的代码，在形式上是高度类似的．这是由于它们使用了相同的状态表示方式和类似的状态转移．也正因为如此，一般来说两种实现的时间复杂度是一样的．

下面给出的是递推实现的代码（为了方便对比，没有添加滚动数组优化），通过对比可以发现二者在形式上的类似性．

---|---

在求解动态规划的问题时，记忆化搜索和递推，都确保了同一状态至多只被求解一次．而它们实现这一点的方式则略有不同：递推通过设置明确的访问顺序来避免重复访问，记忆化搜索虽然没有明确规定访问顺序，但通过给已经访问过的状态打标记的方式，也达到了同样的目的．

与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便地处理边界情况，这是记忆化搜索的一大优势．但与此同时，记忆化搜索难以使用滚动数组等优化，且由于存在递归，运行效率会低于递推．因此应该视题目选择更适合的实现方式．

## 如何写记忆化搜索

### 方法一

  1. 把这道题的 dp 状态和方程写出来
  2. 根据它们写出 dfs 函数
  3. 添加记忆化数组

举例：

𝑑𝑝𝑖 =max{𝑑𝑝𝑗 +1} (1 ≤𝑗 <𝑖 ∧𝑎𝑗 <𝑎𝑖)dpi=max{dpj+1}(1≤j<i∧aj<ai)![](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)（最长上升子序列）

转为

C++Python

---|---

---|---

### 方法二

  1. 写出这道题的暴搜程序（最好是 [dfs](../../search/dfs/)）
  2. 将这个 dfs 改成「无需外部变量」的 dfs
  3. 添加记忆化数组

举例：本文中「采药」的例子

* * *

>  __本页面最近更新： 2026/4/23 03:45:48，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/dp/memo.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/dp/memo.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [interestingLSY](https://github.com/interestingLSY), [Enter-tainer](https://github.com/Enter-tainer), [iamtwz](https://github.com/iamtwz), [ksyx](https://github.com/ksyx), [Tiphereth-A](https://github.com/Tiphereth-A), [Marcythm](https://github.com/Marcythm), [ouuan](https://github.com/ouuan), [Xeonacid](https://github.com/Xeonacid), [cbw2007](https://github.com/cbw2007), [Chrogeek](https://github.com/Chrogeek), [H-J-Granger](https://github.com/H-J-Granger), [Haohu Shen](mailto:haohu.shen@ucalgary.ca), [ImpleLee](https://github.com/ImpleLee), [lailai0916](https://github.com/lailai0916), [luklapse](https://github.com/luklapse), [Menci](https://github.com/Menci), [NachtgeistW](https://github.com/NachtgeistW), [shawlleyw](https://github.com/shawlleyw), [sshwy](https://github.com/sshwy), [StudyingFather](https://github.com/StudyingFather), [Wahacer](https://github.com/Wahacer)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用