在考虑加入「记忆化」时，我们只需要将 DFS 方法签名中的【可变】参数作为维度，DFS 方法中的返回值作为存储值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int n;
  vector<int> stones;
  map<int, int> mp;
  map<int, bool> f;  // 记忆化搜索 cache

  bool canCross(vector<int>& _stones) {
    stones = _stones;
    n = stones.size();
    if (stones[1] != 1) return false;
    for (int i = 0; i < n; i++) mp[stones[i]] = i;  // 反查表
    return dfs(1, 1);
  }
  /**
   * 判定是否能够跳到最后一块石子
   * @param ss 石子列表【不变】
   * @param n  石子列表长度【不变】
   * @param u  当前所在的石子的下标
   * @param k  上一次是经过多少步跳到当前位置的
   * @return 是否能跳到最后一块石子
   */
  bool dfs(int u, int k) {
    int key = u * 10000 + k;  // 计算一个缓存的 key
    if (f.count(key)) return f[key];
    if (u == n - 1) return true;
    for (int i = -1; i <= 1; i++) {
      if (k + i == 0) continue; // 跳过原地踏步的情况
      int next = stones[u] + k + i; // 如果跳 k + i 步，能否落到石头上
      if (mp.count(next)) {
        bool cur = dfs(mp[next], k + i);
        f[key] = cur;
        if (cur) return true;
      }
    }
    f[key] = false;
    return false;
  }
};