记忆化搜索_dfs记忆化搜索

记忆化搜索简介

 记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
 因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。

思想与实现（以采药为例）

 Eg:山洞里有$M$株不同的草药，采每一株都需要一些时间$t_i$，每一株也有它自身的价值$v_i$。给你一段时间$T$，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。

朴素DFS做法

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

void dfs(int pos, int tleft, int tans) {
   
  if (tleft < 0) return;
  if (pos == n + 1) {
   
    ans = max(ans, tans);
    return;
  }
  dfs(pos + 1, tleft, tans);
  dfs(pos + 1, tleft -
1
2
3
4
5
6
7
8
9