#yyds干货盘点# 动态规划专题：滑雪

1.简述：

描述

NowCoder喜欢滑雪，因为滑雪的确很刺激。为了获得速度，必须从高处往低处滑。现在知道某片区域的海拔，如下所示 1  2  3  4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 可以从某个点滑向上下左右四个方向中海拔比当前位置低的点。例如上图中一条可行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1是最长的一条。 现在给出区域的海拔，你能帮忙计算最长的滑道有多长吗？

输入描述:

输入包含多组数据。

每组数据的第一行包含两个正整数m和n (1≤m, n≤100)，紧接着是m*n的海拔矩阵，包含各个点的高度h (1≤h≤10000)。

输出描述:

对应每一组数据，输出该区域最长的滑道长度。

示例1

输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
2 2
1 1
1 1

输出

25
1

2.代码实现：

import java.util.*;

public class Main{

    private static int[][] arr;
    private static int[][] value;
    private static int c;
    private static int r;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            r = sc.nextInt();
            c = sc.nextInt();
            int max = 0;
            arr = new int[r][c];
            value = new int[r][c];
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    int temp = ski(i, j, Integer.MAX_VALUE);
                    if (temp > max) {
                        max = temp;
                    }
                }
            }
            System.out.println(max);

        }
        sc.close();
    }

    /**
     * @param c
     * @param r
     * @param maxValue
     * @return
     */
    private static int ski(int row, int col, int maxValue) {
        if (col >= c || col < 0 || row >= r || row < 0 || maxValue <= arr[row][col] ) {
            return 0;
        }
        if (value[row][col] > 0) {
            return value[row][col];
        }
        value[row][col] = max(ski(row-1, col, arr[row][col]), ski(row+1, col, arr[row][col]), ski(row, col-1, arr[row][col]), ski(row, col+1, arr[row][col])) + 1;
        return value[row][col];
    }

    /**
     * @param ski
     * @param ski2
     * @param ski3
     * @param ski4
     * @return
     */
    private static int max(int ski1, int ski2, int ski3, int ski4) {
        // TODO Auto-generated method stub
        return Math.max(Math.max(ski1, ski2), Math.max(ski3, ski4));
    }

}