侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【记忆化搜索】滑雪

GabrielxD
2022-12-01 / 0 评论 / 1 点赞 / 28 阅读 / 1,050 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-01,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

题目

901. 滑雪


给定一个 RRCC 列的矩阵,表示一个矩形网格滑雪场。

矩阵中第 ii 行第 jj 列的点表示滑雪场的第 ii 行第 jj 列区域的高度。

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

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

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

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

在给定矩阵中,一条可行的滑行轨迹为 24172124-17-2-1

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

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

输入格式

第一行包含两个整数 RRCC

接下来 RR 行,每行包含 CC 个整数,表示完整的二维矩阵。

输出格式

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

数据范围

1R,C3001 \le R,C \le 300 ,
0矩阵中整数100000 \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

解题

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

思路

思维过程:

image-20221201125747978

动态规划:

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

  • 状态转移方程:

    dp[i][j]=max{dp[i1][j]+1g[i1][j]>g[i][j]dp[i][j+1]+1g[i][j+1]>g[i][j]dp[i+1][j]+1g[i+1][j]>g[i][j]dp[i][j1]+1g[i][j1]>g[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}

  • 初始状态:第一次状态转移前,所有位置都只经过了一个格子,滑雪长度是 11,即:
    dp[i][j]=1dp[i][j] = 1i=0r1,j=0c1i = 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];
    }
}
1

评论区