记忆化 DFS

引入

记忆化 DFS，顾名思义，就是带有记忆的深度优先搜索。

总所周知，用程序实现 Fibonacci 数列求值有两种常见方式：

• 通过迭代即非递归的方式：

  int Fibonacci(int n) {
      if (n == 1 || n == 2) {
          return 1;
      }
      int pre = 1, next = 1, sum = 0;
      while (n-- > 2) {
          sum = pre + next;
          pre = next;
          next = sum;
      }
  
      return sum;
  }

• 通过递归方式：

  int Fibonacci(int n) {
      if (n == 1 || n == 2) {
          return 1;
      }
      return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

上述两种方式各有优缺点，迭代方式效率更高，但是写起来比较麻烦；递归方式运行效率低，但是代码实现容易。

有没有一种方式可以结合两者的优点呢？

对于第二种递归方式，其主要的时间开销在于计算了许多重复内容，我们是否可以使用一个数组来维护已经计算过的值呢？

答案是显然的，于是我们就有了 —— 记忆化 DFS：

int fib[MAX_NUM]; // 记忆数组

int Fibonacci(int n) {
    if (fib[n]) {
        return fib[n]; // 已经计算过的值直接返回
    }
    if (n == 1 || n == 2) {
        fib[n] = 1;
    }
    else {
        fib[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
    }

    return fib[n];
}

以上代码以递归的方式实现，但是时间复杂度可以降到线性，和迭代形式一样，不同的地方在于我们需要额外的空间开销来记录已经计算过的值。

可能有同学就有疑问了：

上述例子很容易用 DP 来实现，为什么还需要记忆化 DFS 呢？

接下来我们将给出几个实际例子加以说明。

实例分析

案例一

猫和老鼠

Problem Description 有个小老鼠在校园里收藏了一些它最爱吃的奶酪。 校园可以看成一个长度为n的正方形网格，每个网格可以标记为 (p, q) ，其中，0 <= p , q < n。每个网格都有一个洞，里面储存了 k（0 <= k <= 100）块奶酪。

现在，小老鼠准备享用这些美味啦。

开始的时候，他在 (0, 0) 这个位置，每到一个地方，它都会吃光这个地方的奶酪，然后沿着水平或者垂直的方向到达另外一个地方。麻烦的是，有个很凶的猫总是在它的洞口附近，所以他每次最多移动 k 个位置，否则就会被这只猫吃掉。更糟糕的是，每在一个地方吃过奶酪，小老鼠都会变胖，所以，为了获得足够下一次逃跑的能量，它每次只能去比当前位置的奶酪更多的格子。 现在已知 n 和 k ，以及在每个网格的洞中小老鼠储存的奶酪的数量，请计算小老鼠在无法移动之前，一共最多能吃到多少块奶酪。

Input 题目包含多组测试数据。

每组测试数据组成如下： 首先一行包含2个不超过100的正整数 n 和 k ; 接下来 n 行，每行包含n个数： 第一行 n 个数分别表示 (0, 0), (0, 1), … (0, n - 1) 这些位置储存的奶酪数量； 第二行 n 个数分别表示 (1, 0), (1, 1), … (1, n - 1) 这些位置储存的奶酪数量； 以此类推...

输入数据以两个 -1 结束。

Output 请输出小老鼠最多 能够吃到的奶酪数量，每组数据输出一行。

输入案例：

3 1
1 2 5
10 11 6
12 12 7
-1 -1

输出案例：

37

分析：

根据题意，我们假设从 \((x, y)\) 出发的老鼠可以吃到的最大奶酪数量为 \(ans(x, y)\)，\((x, y)\) 处的芝士储量为 \(cheese(x, y)\)，老鼠可以从 \((x, y)\) 出发在一次 \(k\) 步以内的移动中到达的坐标的集合为 \(S = \{(x_1, y_1), (x_2, y_2), (x_3, y_3), ...\}\)，不难得出状态转移方程： \[ ans(x, y) = max_{(x_n, y_n) \in S} ans(x_n, y_n) \ + \ cheese(x, y) \] 如果直接用动态规划求解，这个问题的处理会相当复杂，因为我们难以从该状态转移方程中确定 DP 的起点和 DP 的方向，所以直接采用迭代的方式恐怕不现实。

于是我们便考虑到可以使用记忆化 DFS，既保证了效率，又降低了编码难度。

代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <array>

using namespace std;

#define MAX_LENG 105

int cheese[MAX_LENG][MAX_LENG];
int ans[MAX_LENG][MAX_LENG]; // 储存结果，初始化为 -1

int n, k;
const vector<array<int, 2>> dirs = {
    {1, 0},
    {0, 1},
    {-1, 0},
    {0, -1}
}; // 运动方向

int dfs(int x, int y) {
    // 记忆化 DFS
    // 返回以 (x, y) 为起点可以吃到最多的奶酪
    if (ans[x][y] >= 0) {
        // 已经计算过的值
        return ans[x][y];
    }
    ans[x][y] = cheese[x][y];
    int plusCheese = 0;
    for (auto& dir :dirs) {
        for (int s = 1; s <= k; s++) {
            int nx = x + s * dir[0];
            int ny = y + s * dir[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && cheese[nx][ny] > cheese[x][y]) {
                plusCheese = max(plusCheese, dfs(nx, ny));
            }
        }
    }

    ans[x][y] += plusCheese;
    return ans[x][y];
}

int main() {

    ios::sync_with_stdio(false);
    while (cin >> n >> k, n != -1 || k != -1) {
        memset(ans, 0xff, sizeof(ans));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> cheese[i][j];
            }
        }
        cout << dfs(0, 0) << endl;
    }

    return 0;
}

案例二

How many ways

Problem Description 这是一个简单的生存游戏，你控制一个机器人从一个棋盘的起始点 (1, 1) 走到棋盘的终点 (n, m)。游戏的规则描述如下：

1. 机器人一开始在棋盘的起始点并有起始点所标有的能量。
2. 机器人只能向右或者向下走，并且每走一步消耗一单位能量。
3. 机器人不能在原地停留。
4. 当机器人选择了一条可行路径后，当他走到这条路径的终点时，他将只有终点所标记的能量。

img

如上图，机器人一开始在 (1, 1) 点，并拥有4单位能量，蓝色方块表示他所能到达的点，如果他在这次路径选择中选择的终点是 (2, 4) ，当他到达 (2, 4) 点时将拥有1单位的能量，并开始下一次路径选择，直到到达 (6, 6) 点。 我们的问题是机器人有多少种方式从起点走到终点。这可能是一个很大的数，输出的结果对 10000 取模。

Input 第一行输入一个整数T,表示数据的组数。 对于每一组数据第一行输入两个整数 n, m (1 <= n, m <= 100)。表示棋盘的大小。接下来输入 n 行,每行 m 个整数 e (0 <= e < 20)。

Output 对于每一组数据输出方式总数对10000取模的结果。

输入案例：

1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2

输出案例：

3948

分析：

同案例一，我们只需找到状态转移方程后使用记忆化 DFS 即可，这里不再赘述。

代码：

#include <iostream>
#include <cstring>

using namespace std;

int T; // 数据组数
int n, m;

#define MAX_LENG 105
#define MAX_NUM 10000

int energy[MAX_LENG][MAX_LENG]; // 记录每个格点点能量
int ans[MAX_LENG][MAX_LENG]; // 记录答案，初始化为 -1

int dfs(int x, int y) {
    // 表示从 (x, y) 出发到终点又多少种走法
    if (ans[x][y] >= 0) {
        return ans[x][y];
    }
    if (x == n - 1 && y == m - 1) {
        ans[x][y] = 1;
        return ans[x][y];
    }
    int power = energy[x][y]; // 能量
    ans[x][y] = 0;
    for (int i = 0; i <= power; i++) {
        for (int j = 0; j <= power - i; j++) {
            // 遍历所有可能位置
            int nx = x + i, ny = y + j;
            if (nx != x || ny != y) {
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    ans[x][y] = (ans[x][y] + dfs(nx, ny)) % MAX_NUM;
                }
            }
        }
    }

    return ans[x][y];
}

int main() {

    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> energy[i][j];
            }
        }
        memset(ans, 0xff, sizeof(ans));
        cout << dfs(0, 0) << endl;
    }


    return 0;
}

在 Python 中的简单实现

在 Python 中，实现记忆化搜索的一个简单方式是使用 functools 模块中的 lru_cache 装饰器。这个装饰器可以告诉 Python 缓存函数的输出值，以便相同的输入参数在后续调用中不需要重新计算。

基本的函数声明如下：

from functools import lru_cache

@lru_cache(maxsize=None)
def f(x):
    # 函数体

在这个例子中，@lru_cache(maxsize=None) 是一个装饰器，它应用于函数 f。这个装饰器会缓存 f 的调用结果，以便相同的输入 x 在将来的调用中可以直接从缓存中获取结果，而不需要重新计算。

• maxsize 参数用于指定缓存的大小。如果设置为 None，缓存的大小是无限的，这意味着除非显式清除，否则所有的调用都会被缓存。
• 如果你想限制缓存的大小，可以设置 maxsize 为一个正整数，这将限制缓存的大小，当达到最大值时，最旧的结果将被移除。