记忆化搜索

定义

记忆化搜索，是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。

理解

搜索是对一个问题不断地寻找可行方案，从初始状态开始，经过一系列状态转移，寻找目标状态或者最优状态。这是一种「通用解题方法」，但是大部分情况下搜索所需的时间复杂度都很高。

在搜索的过程中，可以记录并保存每个状态的搜索结果，在之后重复遍历这个状态时，能够直接检索并得到搜索结果。

具体应用

滑雪

滑雪时，一个人可以从某个点滑向上下左右相邻四个点之一，但是前提条件是滑向的相邻点的高度比当前点要低。现在有一个 N×MN \times M 的滑雪区域，请计算在这个区域中最长的滑雪下坡路径长度，其中每个点最多经过一次。

从每个点出发都可能形成一条滑雪路径，因此需要遍历整个区域，从每个点出发开始一次搜索，最后取最长的路径。每次搜索的过程类似迷宫问题，另外在每一步从当前点走到相邻点时，需要保证当前点的高度大于相邻点的高度。由于这一条件的限制，可以省略标记数组，因为高度低的点无法向高度高的点移动，也就保证了每个点最多经过一次。

朴素的搜索方法时间复杂度过高，考虑记忆化搜索。用一个二维数组 dp 记录从每个点出发的最长滑雪路径，dp[i][j] 表示从 (i, j) 点出发能走的最长路径。对于每个点作为起点的路径，整个过程中只会搜索一次。
例如下面这个例子：
1 1
2 3
先去找 (1,1) 的最长距离，很明显为 1
接着找 (1,2) 的最长距离，很明显为 1
然后找 (2,1) 的最长距离，为 2 ((2,1) -> (1,1))
然后是 (2,2) 的最长距离，如果没有记忆化，那么搜索过程为：(2,2) -> (2,1) -> (1,1)。但是（2,1）之前已经搜索过了，再去搜索就是浪费时间，之前搜索已经知道 (2,1) 的值为 2，那么搜索过程就可以缩短为：(2,2)->(2,1)，用已有的 (2,1) 的值再更新 (2,2) 的值。

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
int n, m;
vector<vector<int>> h; // n * m 的区域，其中 h[i][j] 表示 (i, j) 点的高度
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // 记忆化搜索，用于记录每个点的最长下坡路径长度
int ans = 0; // 记录最终答案

int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}}; // 使用一个数组记录向四个方向移动时横纵坐标的变化

bool check(int x, int y){ // 判断位置 (x, y) 是否位于迷宫边界之外
   if(x >= 1 && x <= n && y >= 1 && y <= m) return true;
   return false;
}

int dfs(int x, int y){
   //记忆化搜索，对于已经搜索过的位置，直接返回搜索结果
   if(dp[x][y]) return dp[x][y];

   dp[x][y] = 1; // 每个点初始路径长度设置为 1

   for(int i = 0; i < 4; i++){ // 四个方向
      int nx = x + dir[i][0];
      int ny = y + dir[i][1];
      if(check(nx, ny) && h[x][y] > h[nx][ny]){ // 下一个点在区域内，并且高度降低，则继续搜索
         dfs(nx, ny);
         dp[x][y] = max(dp[x][y], dp[nx][ny] + 1); // 回溯阶段，用相邻点的结果更新当前点的结果
      }
   }

   return dp[x][y];
}

// 每个点进行一次搜索
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
        ans = max(ans, dfs(i, j));
    }
}
cout << ans << endl;