题解 | 滑雪

import java.util.*;

// 这题求的是长度，每次+1
public class Main {
    static int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt(), n = in.nextInt();
        int[][] arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {                
                arr[i][j] = in.nextInt();
            }
        }
        System.out.println(process(m, n, arr));
    }

    private static int process(int m, int n, int[][] arr) {
        int[][] dp = new int[m][n];
//        for(int i=0;i<m;i++) Arrays.fill(dp[i],1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(i, j, m, n, arr, dp);
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

    private static int  dfs( int i, int j, int m, int n, int[][] arr, int[][] dp) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (dp[i][j] != 0) return dp[i][j];
        int max = 1;
        for (int[] dir : dirs) {
            int ni = i + dir[0], nj = j + dir[1];
            if (ni >= 0 && nj >= 0 && ni < m && nj < n && arr[ni][nj] > arr[i][j]) {
                max = Math.max(max, dfs(ni, nj, m, n, arr, dp) + 1);
            }
        }
        dp[i][j] = max;
        return max;
    }
}