题目描述

给定一个 $n$ 行 $m$ 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 $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$ 个区域。

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

输入格式

第一行包含两个整数 $n$ 和 $m$。

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

输出格式

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

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

提示

【样例 #1 解释】

• $dp[x][y]$ 表示从 $(x, y)$ 出发的最长路，那么有

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

// cal(x, y) 用来计算 dp[x][y], 这是一个递归函数
int cal(int x, int y) {
    // 第 1 步: 终止条件, dp[x][y] 已经计算过
    if (dp[x][y] != -1) return dp[x][y];
    
    // 第 2 步: 转移方程
    dp[x][y] = 1;
    for (int k = 0; k < 4; k++) {
        int u = x + dx[k], v = y + dy[k];
        if (u < 0 || u >= n || v < 0 || v >= m) continue;
        if (a[u][v] < a[x][y]) dp[x][y] = max(dp[x][y], cal(u, v) + 1);  // 这里是 cal(u, v)
    }
    return dp[x][y];
};

• 由于每个状态最多只会计算一次，因此时间复杂度是 状态数*转移代价，即 $O(n*m*4)$
• 这种用递归函数来求解动态规划问题的方法，我们一般称之为 记忆化搜索

数据规模与限制

$1 \le n,m \le 300$,
$0 \le 矩阵中整数 \le 10000$