动态规划-滑雪java

import java.util.Scanner;

public class Main {
   static Scanner sc = new Scanner(System.in);
   static int[][] place;
   static int[][] dp;
   //java不支持静态数组的初始化
   static int dx[] = {0, 1, 0, -1};
   static int dy[] = {1, 0, -1, 0};
   static int r, c;
   static int maxl;

   public static int dfs(int x, int y) {
       //判断是否访问过
       if (dp[x][y] != 0) {
           return dp[x][y];
       }
       dp[x][y] = 1;
       int m = 0;//四个方向上的最长路径
       for (int i = 0; i < 4; i++) {
           int nx = x + dx[i];
           int ny = y + dy[i];
           //判断是否越界
           if (nx < 1 || ny < 1 || nx > r || ny > c) {
               continue;  //跳出本次循环
           }
           //检查新的位置是否大于当前位置（我们要找小的位置滑下去）
           if (place[nx][ny] >= place[x][y]) {
               continue;
           }
           m = Math.max(m, dfs(nx, ny));
       }
       dp[x][y] += m;
       maxl = Math.max(maxl, dp[x][y]);
       return dp[x][y];
   }

   public static void main(String[] args) {
       r = sc.nextInt();
       c = sc.nextInt();
       place = new int[r + 1][c + 1];
       dp = new int[r + 1][c + 1];
       for (int i = 1; i <= r; i++) {
           for (int j = 1; j <= c; j++) {
               place[i][j] = sc.nextInt();
           }
       }

       for (int i = 1; i <= r; i++) {
           for (int j = 1; j <= c; j++) {
               dfs(i, j);
           }
       }

       System.out.println(maxl);
   }
}