记忆化搜索

想体验把暴搜改改就是正解的快感吗？想体验状压 dp 看似状态多到爆炸实际一跑却嗷嗷快（实际有效的状态数很少）的荣耀吗？记忆化搜索，符合您的需求！只要 998 , 记忆化搜索带回家！记忆化搜索，记忆化搜索，再说一遍，记忆化搜索！

记忆化搜索是啥¶

好，就以洛谷 P1048 采药为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的DFS:

注：为了方便食用，本文中所有代码省略头文件

int n, t;
int tcost[103], mget[103];
int ans = 0;
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 - tcost[pos], tans + mget[pos]);
}
int main() {
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  dfs(1, t, 0);
  cout << ans << endl;
  return 0;
}

这就是个十分智障的大暴搜是吧 ......

emmmmmm....... 分

然后我心血来潮，想不借助任何 "外部变量"（就是 dfs 函数外且 值随 dfs 运行而改变的变量 ), 比如 ans

把 ans 删了之后就有一个问题：我们拿什么来记录答案？

答案很简单：

返回值！

此时返回在时间内采集后个草药，能获得的最大收益

不理解就看看代码吧：

int n, time;
int tcost[103], mget[103];
int dfs(int pos, int tleft) {
  if (pos == n + 1) return 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos]) dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
  return max(dfs1, dfs2);
}
int main() {
  cin >> time >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, time) << endl;
  return 0;
}

~~emmmmmm....... 还是分~~

但这个时候，我们的程序已经不依赖任何外部变量了。

然后我非常无聊，将所有 dfs 的返回值都记录下来，竟然发现……

震惊，对于相同的 pos 和 tleft,dfs 的返回值总是相同的！

想一想也不奇怪，因为我们的 dfs 没有依赖任何外部变量。

旁白：像 , 这种东西不算是外部变量，因为她们在 dfs 过程中不变。

然后？

开个数组 , 记录下来每个的返回值。刚开始把中每个值都设成（代表没访问过）。每次刚刚进入一个 dfs 前（我们的 dfs 是递归调用的嘛），都检测是否为 , 如果是就正常执行并把答案记录到中，否则？

直接返回中的值！

int n, t;
int tcost[103], mget[103];
int mem[103][1003];
int dfs(int pos, int tleft) {
  if (mem[pos][tleft] != -1) return mem[pos][tleft];
  if (pos == n + 1) return mem[pos][tleft] = 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos]) dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
  return mem[pos][tleft] = max(dfs1, dfs2);
}
int main() {
  memset(mem, -1, sizeof(mem));
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, t) << endl;
  return 0;
}

此时的意义与 dfs 相同：

在时间内采集后个草药，能获得的最大收益

这能 ac ?

能。 这就是 "采药" 那题的 AC 代码

好我们 yy 出了记忆化搜索

总结一下记忆化搜索是啥：¶

不依赖任何 外部变量
答案以返回值的形式存在，而不能以参数的形式存在（就是不能将 dfs 定义成 , 这里面的 nowans 不符合要求）。
对于相同一组参数，dfs 返回值总是相同的