【算法】记忆化搜索

记忆化搜索也是一种剪枝策略。通过一个 “备忘录”，记录第一次搜索到的结果，当下一次搜索到这个状态时，直接在 “备忘录” 里面找结果。记忆化搜索，有时也叫动态规划。

1. 如何实现记忆化搜索？

• 创建备忘录。
• 递归的时候，先查看备忘录中是否存在结果。
• 递归返回的时候，先将结果存到备忘录中。

2. 所有的递归以及暴搜，都能用记忆化搜索来进行优化吗？只有在递归的过程中，出现了大量 “完全相同的问题” 时，才能用记忆化搜索优化。
3. 注意：初始化备忘录时，一定不能存在递归过程中可能出现的值。

1.斐波那契数

斐波那契数

解法：记忆化搜索

在搜索的过程中，如果发现特别多完全相同的子问题，就可以添加一个备忘录，将搜索的结果放在备忘录中。下一次在搜索到这个状态时，直接在备忘录里面拿值。

class Solution 
{
    int f[35]; //备忘录

public:
    int dfs(int n)
    {
        //搜索之前先查看备忘录中是否存在结果
        if(f[n] != -1) return f[n];

        if(n == 0 || n == 1) return n;

        //返回之前，将结果存放在备忘录中
        return f[n] = dfs(n - 1) + dfs(n - 2);
    }

    int fib(int n) 
    {
        //先初始化备忘录成一定不会存在的值
        memset(f, -1, sizeof(f));
        return dfs(n);
    }
};

2.Function

P1464 Function

解法：记忆化搜索

题目叙述的非常清楚，我们仅需按照「题目的要求」把「递归函数」写出来即可。但是，如果不做其余处理的话，结果会「超时」。因为我们递归的「深度」和「广度」都非常大。通过把「递归展开图」画出来，我们发现，在递归过程中会遇到大量「一模一样」的问题，如下图（因为递归展开过于庞大，这里只画出了一部分）：

因此，可以在递归的过程中，把每次算出来的结果存在一张「备忘录」里面。等到下次递归进入「一模一样」的问题之后，就「不用傻乎乎的展开计算」，而是在「备忘录里面直接把结果拿出来」，起到大量剪枝的效果。

#include<iostream>
using namespace std;

typedef long long LL;

const int N = 25;

LL a, b, c;
LL f[N][N][N]; //备忘录

LL dfs(LL a, LL b, LL c)
{
    //先判断边界情况：防止备忘录数组f越界
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    if(a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
    
    //再查看备忘录中是否存在结果
    if(f[a][b][c]) return f[a][b][c];
    
    if(a < b && b < c)
        return f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);
    else
        return f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
}

int main()
{
    while(cin >> a >> b >> c)
    {
        //多组测试数据：不需要清空
        if(a == -1 && b == -1 && c == -1) break;
        
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c));
    }
    
    return 0;
}

3.天下第一

P5635 【CSGRound1】天下第一

解法：记忆化搜索

用递归模拟整个游戏过程：dfs(x, y) 的结果可以由 dfs((x + y) % p, (x + y + y) % p) 得到。因为测试数据是多组的，并且模数都是 p，再加上递归的过程中会递归的相同的问题，所以可以把递归改写成记忆化搜索。其中：

1. f[x][y] = 1，表示 cbw 赢。
2. f[x][y] = 2，表示 zhouwc 赢。
3. f[x][y] = 3，表示这个位置已经被访问过，如果没被修改成 1 或者 2，那就表明平局。

注意事项：这道题的数据范围很大，用 int 类型创建二维数组空间会溢出。但是我们的最终结果仅有三种情况，所以可以用 char 类型来存储最终结果，节省空间。

#include<iostream>
using namespace std;

const int N = 1e4 + 10;

int x, y, p;
char f[N][N]; //备忘录

char dfs(int x, int y)
{
    //查看备忘录中是否存在结果
    if(f[x][y]) return f[x][y];
    
    //没有结果时表示：这个状态已经访问过了, 之后再遇到时, 表示平局 
    f[x][y] = '3';
    
    //修改为正确的结果再返回, 否则该位置是'3'
    if(x == 0) return f[x][y] = '1'; 
    if(y == 0) return f[x][y] = '2';
    
    //同理: 修改为正确的结果再返回
    return f[x][y] = dfs((x + y) % p, (x + y + y) % p);
}

int main()
{
    int T; cin >> T >> p;
    while(T--)
    {
        cin >> x >> y;
        char ret = dfs(x, y);
        if(ret == '1') cout << 1 << endl;
        else if(ret == '2') cout << 2 << endl;
        else cout << "error" << endl;
    }
    
    return 0;
}

4.滑雪

P1434 [SHOI2002] 滑雪

解法：记忆化搜索

暴力枚举：遍历整个矩阵，看看以当前位置为起点，最远能滑行多远的距离。在所有情况里面，取最大值即可。

如何求出以 [i, j] 为起点的最大距离？

1. 从 [i, j] 位置上下左右瞅一瞅，如果能滑过去，就看看以下一个位置为起点，最远能滑行多远的距离。
2. 找出四个方向上的最远距离，然后 +1。

因为出现相同子问题，所以可以用 dfs 来解决。又因为在搜索的过程中会遇到一模一样的问题，因此可以把递归改成记忆化搜索的方式。

#include<iostream>
using namespace std;

const int N = 110;

int n, m;
int a[N][N];
int f[N][N]; //备忘录

//上下左右四个方向
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dfs(int i, int j)
{
    if(f[i][j]) return f[i][j]; //先查看备忘录中是否存在结果
    
    int len = 1;
    for(int k = 0; k < 4; k++)
    {
        int x = i + dx[k], y = j + dy[k];
        if(x >= 1 && x <= n && y >= 1 && y <= m && a[i][j] > a[x][y])
        {
            len = max(dfs(x, y) + 1, len);
        }
    }
    return f[i][j] = len; //先往备忘录中存，再返回最大滑坡
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    
    int ret = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            ret = max(ret, dfs(i, j));
        }
    }
    cout << ret << endl;
    
    return 0;
}