【记忆化搜索】滑雪

【动态规划, 记忆化搜索】滑雪

题目

901. 滑雪

---

给定一个 $R$ 行 $C$ 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 $i$ 行第 $j$ 列的点表示滑雪场的第 $i$ 行第 $j$ 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

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-2-1$ 。

在给定矩阵中，最长的滑行轨迹为 $25-24-23-…-3-2-1$ ，沿途共经过 $25$ 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 $R$ 和 $C$ 。

接下来 $R$ 行，每行包含 $C$ 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

$1 \le R,C \le 300$ ,
$0 \le 矩阵中整数 \le 10000$

输入样例：

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

输出样例：

25

解题

方法一：动态规划 记忆化搜索

思路

思维过程：

动态规划：

• 状态定义：$dp[i][j]$ 表示所有从 $(i, j)$ 开始滑的路径中滑雪轨迹最长的长度。

• 状态转移方程：

  $$dp[i][j] = \max \begin{cases} dp[i-1][j] + 1 & g[i-1][j] > g[i][j] \\ dp[i][j+1] + 1 & g[i][j+1] > g[i][j] \\ dp[i+1][j] + 1 & g[i+1][j] > g[i][j] \\ dp[i][j-1] + 1 & g[i][j-1] > g[i][j] \\ \end{cases}$$

• 初始状态：第一次状态转移前，所有位置都只经过了一个格子，滑雪长度是 $1$，即：
  $dp[i][j] = 1$ （$i = 0\dots r-1,j=0\dots c - 1$）。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int r, c;
    static int[][] g, dp;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        r = (int) in.nval;
        in.nextToken();
        c = (int) in.nval;
        g = new int[r][c];
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                in.nextToken();
                g[i][j] = (int) in.nval;
            }
        }
        dp = new int[r][c];
        for (int[] row : dp) Arrays.fill(row, -1);
        int max = 0;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                max = Math.max(max, dfs(i, j));
            }
        }
        System.out.println(max);
    }
    
    static int dfs(int x, int y) {
        if (dp[x][y] != -1) return dp[x][y];
        dp[x][y] = 1;
        for (int[] DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx >= 0 && nx < r && ny >= 0 && ny < c && g[nx][ny] > g[x][y]) {
                dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
            }
        }
        return dp[x][y];
    }
}