poj 1088 滑雪

poj 1088 滑雪

记忆化搜索

import java.util.*;
public class Main{
    static int n, m;
    static int[] dx, dy;
    static int[][] dp, a;
    static int f(int i, int j) {
        if(dp[i][j] != -1) return dp[i][j];
        boolean finished = false;
        for(int k=0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && a[i][j] > a[x][y]) {
                dp[x][y]=f(x, y);
                dp[i][j] = Math.max(dp[i][j], 1 + dp[x][y]);
                finished = true;
            }
        }
        if(!finished) dp[i][j] = 1;
        return dp[i][j];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); m = sc.nextInt();
        a = new int[n][m];
        dp = new int[n][m];
        for(int i=0; i < n; i++) {
            for(int j=0; j < m; j++){
                a[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }
        dx = new int[] {1, 0, -1, 0};
        dy = new int[] {0, 1, 0, -1};
        for(int i=0; i < n; i++)
            for(int j=0; j < m; j++)
                f(i, j);
        int res = 0;
        for(int i=0; i < n; i++)
            for(int j=0; j < m; j++)
                res = Math.max(res, dp[i][j]);
        System.out.println(res);
    }
}