C++知识点总结(40)：深度优先搜索（DFS）的记忆化搜索_c++记忆化搜索

一、概念

1. 剪枝优化

2. 记忆化搜索

在某个问题中，可能会存在一些子问题的解在后续计算中被重复使用，而记忆化搜索通过记录已经计算得到的子问题解，以便后续直接使用，避免重复计算，从而提高算法效率。

二、例题

1. 斐波那契数列

1.1 审题

计算斐波那契数列第 $n$（$1\le n\le 50$）项的值。

1.2 参考答案

一般情况下，我们写出如下代码：

#include <iostream>
using namespace std;

long long n;

long long Fib(int n)
{
	// 边界 
	if (n==1 || n==2)
		return 1;
	
	// 递归
	return Fib(n-1)+Fib(n-2); 
}

int main()
{
	cin >> n;
	cout << Fib(n);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

然后因为 $1\le n\le 50$ 这个数据范围，我们需要用空间换时间，使用记忆化搜索的方法，将 $F(3),F(4),...$ 存储到 a[] 数组中，从而减少时间复杂度。

#include <iostream>
using namespace std;

long long n;
long long a[55];

long long Fib(int n)
{
	// 边界 
	if (n==1 || n==2)
		return 1;
	
	// 赋值
	if (a[n] != 0)
		return a[n]; 
	
	// 递归
	return a[n]=Fib(n-1)+Fib(n-2); 
}

int main()
{
	cin >> n;
	cout << Fib(n);
	return 0;
}
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

2. 魔法函数

2.1 审题

有一个神秘的魔法函数 magic(a,b,c)。这个魔法函数的威力取决于 $a,b,c$ 三个数的值，并且这个函数的运行规则非常复杂：

• 如果 $a\le 0$ 或 $b\le 0$ 或 $c\le 0$，那么魔法的威力为$1$。
• 如果 $a>20$ 或 $b>20$ 或 $c>20$，那么魔法的威力等于 magic(20,20,20) 的威力。 - 如果 $a<b$ 并且 $b<c$，那么魔法的威力等于 magic(a,b,c-1) + magic(a,b-1,c-1) - magic(a,b-1,c) 的威力。
• 其他情况下，魔法的威力等于 magic(a-1,b,c) + magic(a-1,b-1,c) + magic(a-1,b,c-1) - magic(a-1,b-1,c-1) 的威力。
• 同时几个条件的时候，应该按照最先满足的条件来计算。

现在输入若干行 $a,b,c$（保证不超过 long long 范围），以 -1 -1 -1 为结束。

2.2 思路

按照题目的描述，我们有如下函数：
m a g i c ( a , b , c ) = { 1 if  a ≤ 0  or  b ≤ 0  or  c ≤ 0 m a g i c ( 20 , 20 , 20 ) if  a > 20  or  b > 20  or  c > 20 m a g i c ( a , b , c − 1 ) + m a g i c ( a , b − 1 , c − 1 ) − m a g i c ( a , b − 1 , c ) if  a < b  and  b < c m a g i c ( a − 1 , b , c ) + m a g i c ( a − 1 , b − 1 , c ) + m a g i c ( a − 1 , b , c − 1 ) − m a g i c ( a − 1 , b − 1 , c − 1 ) otherwise magic(a,b,c) =

$$\begin{cases} 1 & \text{if } a \leq 0 \text{ or } b \leq 0 \text{ or } c \leq 0 \\ magic(20,20,20) & \text{if } a > 20 \text{ or } b > 20 \text{ or } c > 20 \\ magic(a,b,c-1) + magic(a,b-1,c-1) - magic(a,b-1,c) & \text{if } a < b \text{ and } b < c \\ magic(a-1,b,c) + magic(a-1,b-1,c) + magic(a-1,b,c-1) - magic(a-1,b-1,c-1) & \text{otherwise} \end{cases}$$ magic(a,b,c)=⎩ ⎨ ⎧​1magic(20,20,20)magic(a,b,c−1)+magic(a,b−1,c−1)−magic(a,b−1,c)magic(a−1,b,c)+magic(a−1,b−1,c)+magic(a−1,b,c−1)−magic(a−1,b−1,c−1)​if a≤0 or b≤0 or c≤0if a>20 or b>20 or c>20if a<b and b<cotherwise​

2.3 参考答案

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;

ll a, b, c;
ll n[25][25][25];

ll magic(ll a, ll b, ll c)
{
    if (a<=0 || b<=0 || c<=0) return 1;
    if (a>20 || b>20 || c>20) return magic(20, 20, 20);
    if (n[a][b][c] != 0) return n[a][b][c];
    if (a<b && b<c) return n[a][b][c]=magic(a, b, c-1)+magic(a, b-1, c-1)-magic(a, b-1, c);
    return n[a][b][c]=magic(a-1, b, c)+magic(a-1, b-1, c)+magic(a-1, b, c-1)-magic(a-1, b-1, c-1);
}

int main()
{
    freopen("magic.in", "r", stdin);
    freopen("magic.out", "w", stdout);
    
    while (cin >> a >> b >> c)
        if (a==-1 && b==-1 && c==-1)
            break;
        else
            cout << magic(a, b, c) << endl;
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}
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

3. [SHOI 2002] 滑雪

3.1 审题

滑雪为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。求在一个区域中最长滑坡的长度。区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
1
2
3
4
5

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 $24-17-16-1$（从 $24$ 开始，在 $1$ 结束）。$25-24-23-......-3-2-1$ 是最长的一条。

3.2 思路

枚举每一个起点，记忆化搜索的是保留每一个点的最长路径。

3.3 参考答案

#include <iostream>
using namespace std;

int n, m;
int a[105][105];
int maxlen[105][105]; // 每个点的最长距离
int dx[5] = {-1, 0, 0, 1};
int dy[5] = {0, -1, 1, 0};
int ans = -1e8;

// 计算每个点的路径最大长度
int dfs(int x, int y)
{
    // 剪枝
    if (maxlen[x][y] != 0) return maxlen[x][y];
    
    // 遍历四个方向
    for (int i = 0; i < 4; i++)
    {
        int tx = x+dx[i];
        int ty = y+dy[i];
        
        if (tx>=1 && tx<=n && ty>=1 && ty<=m) // 未到边界
            if (a[tx][ty] < a[x][y]) // 是下坡
            {
                maxlen[x][y] = max(maxlen[x][y], dfs(tx, ty)+1);
            }
    }
    
    return maxlen[x][y];
}

int main()
{
    // 输入
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    // 遍历起点找路径
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, dfs(i, j));
    
    // 输出，不要忘了起点
    cout << ans+1;
    return 0;
}
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
40
41
42
43
44
45
46
47
48
49

4. Apple Catching

4.1 审题

题目描述

很少有人知道奶牛爱吃苹果，农场主约翰的农场上有两棵苹果树（编号为 $1$ 和 $2$），每一棵树上都长满了苹果。奶牛贝茜无法摘下树上的苹果，所以它只能等待苹果从树上落下。但是，由于苹果掉到地上会摔烂，贝茜必须在半空中接住苹果，贝茜吃东西很快，它接到苹果后仅用几秒钟就能吃完。每一分钟，两棵苹果树其中的一棵会掉落一个苹果。贝茜已经经过了足够的训练，只要站在树下就一定能接住这棵树上掉落的苹果。同时，贝茜能够在两棵树之间快速移动（移动时间远少于 $1$ 分钟），因此当苹果掉落时，它必定站在两棵树其中的一棵下面。此外，奶牛不愿意不停地往返于两棵树之间，因此会错过一些苹果。苹果每分钟掉落一个，共 $T$ 分钟，贝茜最多愿意移动 $W$ 次。现给出每分钟掉落苹果的树的编号，要求判断贝茜能够接住的最多苹果数。开始时，贝茜在 $1$ 号树下。

输入描述

第一行 $2$ 个整数 $T,W$，接下来 $T$ 行，每行一个数字，表示在时刻 $t$ 苹果是从 $1$ 号苹果树还是从 $2$ 号苹果树掉下来的。

输出描述

输出一行一个数，表示贝茜最多接到的苹果数量。

样例1

输入

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

输出

6
1

提示

$1\le T\le 1000$，$1\le W\le 30$。

4.2 思路

苹果来了的时候，奶牛只有两种选择：移动或者不移动。首先明确 dfs 函数：

• 参数：
  • 当前时间 ti
  • 当前奶牛位置 pos
  • 当前移动次数 move
• 边界：$T$ 分钟
• 移动条件：
  • 当前位置和苹果下落的位置不相等
  • 移动的次数 $<W$
• 目的：计算当前时间移动了 move 次，在 pos 的位置下，接的苹果个数
• 核心：设置变量 tsum 和 fsum 计算移动和不移动的时间，并且用 max 函数进行取值。

4.3 参考答案

#include <iostream>
using namespace std;

int T; // T: 苹果掉落了T分钟
int W; // W: 最多移动W次
int a[1005]; // a[i]: 第i分钟掉落苹果的位置
int n[1005][35][5]; // n[i][j][k]见ti, move, pos

// ti: 第ti个苹果
// move: 移动的次数
// pos: 奶牛当前位置
int dfs(int ti, int move, int pos)
{
    // 边界&剪枝
    if (ti > T) return 0;
    if (n[ti][move][pos] != 0) return n[ti][move][pos];
    
    int tsum = 0, fsum = 0;
    // 移动
    if (pos!=a[ti] && move<W)
        tsum = dfs(ti+1, move+1, a[ti])+1;
    
    // 不移动
    fsum = dfs(ti+1, move, pos)+((pos==a[ti])?1:0);
    
    return n[ti][move][pos]=max(tsum, fsum);
}

int main()
{
    // 输入
    cin >> T >> W;
    for (int i = 1; i <= T; i++)
        cin >> a[i];
    
    // 输出
    cout << dfs(1, 0, 1);
    return 0;
}
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