题解 | 滑雪

import java.util.*;

public class Main {
    static int n;
    static int m;
    static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        int[][] graph = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                graph[i][j] = in.nextInt();
            }
        }

        int[][] dp = new int[n][m]; // dp[i][j]表示从点(i, j)开始的最长滑行路径长度
        int res = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) { // 遍历整个矩阵
                res = Math.max(res, dfs(graph, dp, i, j)); // 计算从每个点出发的最长路径
            }
        }

        System.out.println(res);
    }

    static int dfs(int[][] graph, int[][] dp, int x, int y) {
        if (dp[x][y] != 0) {
            return dp[x][y]; // 如果已经计算过，直接返回结果
        }

        dp[x][y] = 1; // 初始化为1，表示至少包含当前点
        for (int[] dir : dirs) {
            int curX = x + dir[0];
            int curY = y + dir[1];
            if (curX >= 0 && curX < n && curY >= 0 && curY < m && graph[curX][curY] < graph[x][y]) {
                dp[x][y] = Math.max(dp[x][y], dfs(graph, dp, curX, curY) + 1);
            }
        }

        return dp[x][y];
    }
}

深度优先搜索+动态规划