poj1088动态规划记忆化搜索

import java.util.Scanner;

public class poj1088 {
    static int a[][] = new int[102][102];
    static int f[][] = new int[102][102];
    static int r, c;
    public static void main(String[] args) {
        int longestdistanace = Integer.MIN_VALUE;
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                 f[i][j]=dp(i, j);
                 longestdistanace=Math.max(f[i][j],longestdistanace);
            }
        }
        System.out.println(longestdistanace);
        sc.close();
    }

    public static int dp(int i, int j) {
        int max = 0;
        int tmp;
        if (i < 1 || j < 1 || i >r || j > c)//边界情况
        {
            return 0;
        }
        if (f[i][j] != 0)//记忆化搜索
        {
            return f[i][j];
        }
        if (a[i][j] > a[i][j + 1]) {
            tmp = dp(i, j + 1);
            max = Math.max(max, tmp);
        }
        if (a[i][j] > a[i][j -1]) {
            tmp = dp(i, j - 1);
            max = Math.max(max, tmp);
        }
        if (a[i][j] > a[i-1][j]) {
            tmp = dp(i-1, j);
            max = Math.max(max, tmp);
        }
        if (a[i][j] > a[i+1][j ]) {
            tmp = dp(i+1, j );
            max = Math.max(max, tmp);
        }
       return max+1;

    }
}