记忆化搜索

例题¶

在具体讲何为「记忆化搜索」前，先来看如下的例题：

NOIP 2005 采药

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

DFS 做法¶

注：为了节省篇幅，本文中所有代码省略头文件。

// C++ Version
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;
}

# Python Version
tcost = [0] * 103
mget = [0] * 103
ans = 0

def dfs(pos, tleft, tans):
    global ans
    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])

t, n = map(lambda x:int(x), input().split())
for i in range(1, n + 1):
    tcost[i], mget[i] = map(lambda x:int(x), input().split())
dfs(1, t, 0)
print(ans)

这就是个十分朴素的大暴搜是吧……

emmmmmm…… 分。

优化一¶

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

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

答案很简单：

返回值！

此时 dfs(pos,tleft) 返回在时间 tleft 内采集后 pos 个草药，能获得的最大收益

不理解就看看代码吧：

// C++ Version
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;
}

# Python Version
tcost = [0] * 103
mget = [0] * 103

def dfs(pos, tleft):
    if pos == n + 1:
        return 0
    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)

time, n = map(lambda x:int(x), input().split())
for i in range(1, n + 1):
    tcost[i], mget[i] = map(lambda x:int(x), input().split())
print(dfs(1, time))

emmmmmm……还是 30 分。

但这个时候，dfs 函数已经不需要借助任何外部变量了。

优化二¶

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

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

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

注：tcost、mget 这两个数组不算是外部变量，因为它们的值在 dfs 过程中不会被改变。

然后？

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

直接返回 mem 中的值！

// C++ Version
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;
}

# Python Version
tcost = [0] * 103
mget = [0] * 103
mem = [[-1 for i in range(1003)] for j in range(103)]
def dfs(pos, tleft):
    if mem[pos][tleft] != -1:
        return mem[pos][tleft]
    if pos == n + 1:
        mem[pos][tleft] = 0
        return mem[pos][tleft]
    dfs1 = dfs2 = -INF
    dfs1 = dfs(pos + 1, tleft)
    if tleft >= tcost[pos]:
        dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos]
    mem[pos][tleft] = max(dfs1, dfs2)
    return mem[pos][tleft]


t, n = map(lambda x:int(x), input().split())
for i in range(1, n + 1):
    tcost[i], mget[i] = map(lambda x:int(x), input().split())
print(dfs(1, t))

此时 mem 的意义与 dfs 相同：

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

这能 AC？

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

这就是记忆化搜索。

总结¶

记忆化搜索的特征：

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