一般的dfs, 超时

import java.io.*;
class Main {
    static int N = 310;
    static int[][] a = new int[N][N];
    static int n, m;
    static int mlen;
    static void dfs(int x, int y, int len) {
        if (len > mlen) mlen = len; 

        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int xi = x + dx[i], yi = y + dy[i];
            if (xi < n && xi >= 0 && yi < m && yi >= 0 && a[xi][yi] < a[x][y]) {
                dfs(xi, yi, len + 1);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        for (int i = 0; i < n; i++) {
            s = cin.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(s[j]);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dfs(i, j, 1);
            }
        }
        System.out.println(mlen);
    }
}

dp优化，记忆化搜索dfs

思想：将每一次搜索的位置能走的最大长度保存到 f 中， 避免重复计算

import java.io.*;
class Main {
    static int N = 310;
    static int[][] a = new int[N][N];
    static int[][] f = new int[N][N];
    static int n, m;
    static int dp(int x, int y) {
        if (f[x][y] != 0) return f[x][y];

        f[x][y] = 1;
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int xi = x + dx[i], yi = y + dy[i];
            if (xi < n && xi >= 0 && yi < m && yi >= 0 && a[xi][yi] < a[x][y]) {
                f[x][y] = Math.max(f[x][y], dp(xi, yi) + 1);
            }
        }
        return f[x][y];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        for (int i = 0; i < n; i++) {
            s = cin.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(s[j]);
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, dp(i, j));
            }
        }
        System.out.println(res);
    }
}