记忆化搜索
思想
是实现 DP 的一种手段。
优点：
- 不关心递推顺序；
- 对于两维及以上的 DP，方便处理初始状态和无效状态。
缺点：
无法使用滚动数组。
注意事项：
- 要什么状态搜什么状态；
- 所有的状态转移都要采取直接搜索的数据
很傻。 - 越界的状态不能赋值。
实现步骤：
- 先判断是否越界，如果越界则返回对结果不会造成影响的结果，比如求最大值就返回极小值，求方案数就返回 \(0\)；
- 判断是否已经搜索；
- 判断障碍物；
- 判断是否可以结束搜索（是否到达初始状态）；
- 处理普通状态转移。
例题
P1057 [NOIP2008 普及组] 传球游戏
思路
设 dfs(step, p) 表示在 \(step\) 步传到了 \(p\) 的方案数。
当 dfs(0, 0) 时返回 \(1\)；
否则当 step 不等于 \(0\) 的时候返回 dfs(u - 1, (x + 1) % n) + dfs(u - 1, ((x - 1) + n) % n)。
特别注意假设将 dfs(a, b) 的结果记录在 \(f_{i, j}\) 中，那么不能用 \(f_{i, j}\) 来判断是否搜索过，而是记录 \(vis_{a, b}\)，表示是否遍历过，因为 \(f_{i, j} = 0\) 也有可能表示它没有方案数而不是没有访问过。如果直接判断 \(f_{i, j}\) 是否不等于 \(0\) 会导致 TLE。（或者 memset 成一个别的数字然后特判）。
代码
/*******************************
| Author: SunnyYuan
| Problem: P1057 [NOIP2008 普及组] 传球游戏
| OJ: Luogu
| URL: https://www.luogu.com.cn/problem/P1057
| When: 2023-10-27 20:46:49
|
| Memory: 125 MB
| Time: 1000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
int f[N][N];
bool vis[N][N];
int n, m;
int dfs(int u, int x) {
if (!u) return f[u][x] = (x == 0);
if (vis[u][x]) return f[u][x];
vis[u][x] = true;
return f[u][x] = dfs(u - 1, (x + 1) % n) + dfs(u - 1, ((x - 1) + n) % n);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
cout << dfs(m, 0) << '\n';
return 0;
}