5、记忆化搜索

AcWing 901. 滑雪

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int N = 310;
    int n, m;
    int[][] h = new int[N][N];
    int[][] f = new int[N][N];

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

    //返回从x，y这个点出发的最大路径长度
    int dp(int x, int y) {
        if (f[x][y] != -1) return f[x][y];
        f[x][y]=1;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) {
                f[x][y] = Math.max(f[x][y], dp(a, b) + 1);
            }
        }
        return f[x][y];
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < f.length; i++) {
            Arrays.fill(f[i], -1);
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                h[i][j] = sc.nextInt();
        int res = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                res = Math.max(res, dp(i, j));
        System.out.println(res);
    }
}