AcWIng 901 滑雪 记忆化搜索

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

 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

在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。

在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 R 和 C。

接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300
0≤矩阵中整数≤100000

输入样例：

5 5
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

输出样例：

25

记忆化搜索的本质就是将深度优先搜索的过程，通过避免重复计算同一个状态的结果，从而将时间复杂度优化到多项式复杂度。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define IOS \
    ios::sync_with_stdio(false); \
    cin.tie(0); \
    cout.tie(0)
const int N = 310;
int f[N][N];
int h[N][N];
int r,c;

int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};
int dp(int i,int j){
    if (f[i][j] != -1) return f[i][j];// 已经计算过答案，直接返回

    f[i][j] = 1; // (i,j)这个点可以走，长度至少是1
    for (int t = 0;t < 4;t ++){// 枚举四个方向
        int a = i + dx[t],b = j + dy[t];
        // 判断方向是否在场内且高度合理
        if (a >= 1 && a <= r && b >= 1 && b <= c && h[a][b] < h[i][j])
            f[i][j] = max(f[i][j],dp(a,b) + 1);// 递归
    }
    return f[i][j];
}

int main(){
    IOS;
    cin >> r >> c;

    for (int i = 1;i <= r;i ++)
        for (int j = 1;j <= c;j ++) cin >> h[i][j];

    memset(f,-1,sizeof f);// 初始化为-1

    int res = 0;
    for (int i = 1;i <= r;i ++)
        for (int j = 1;j <= c;j ++)
            res = max(res,dp(i,j));
    cout << res << '\n';
    return 0;
}

if(v!=-1) return v;如果已经计算过了就直接返回,避免重复计算