华为OD机试 - 跳格子3 - 动态规划（Java 2024 C卷 200分）

桃扇骨 2024-04-25 08:43 77阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

小明和朋友们一起玩跳格子游戏，

每个格子上有特定的分数 score = \[1, -1, -6, 7, -17, 7\]，

从起点score\[0\]开始，每次最大的步长为k，请你返回小明跳到终点 score\[n-1\] 时，能得到的最大得分。

### 二、输入描述 ###

第一行输入总的格子数量 n

第二行输入每个格子的分数 score\[i\]

第三行输入最大跳的步长 k

### 三、输出描述 ###

输出最大得分

备注：

1.  格子的总长度 n 和步长 k 的区间在 \[1, 100000\]
2.  每个格子的分数 score\[i\] 在 \[-10000, 10000\] 区间中

#### 1、输入 ####

6  
1 -1 -6 7 -17 7  
2

#### 2、输出 ####

#### 3、说明 ####

输出最大得分数，小明从起点score\[0\]开始跳，第一次跳score\[1\],第二次跳到score\[3\],第三次跳到score\[5\]，因此得到的最大的得分是score\[0\] + score\[1\] + score\[3\] + score\[5\] = 14

### 四、解题思路 ###

这个问题可以通过动态规划的方法来解决。

在这种方法中，我们将定义一个 dp 数组，其中 dp\[i\] 表示到达第 i 个格子时能得到的最大得分。我们将利用步长限制 k，从前 k 个可能的格子中选择最大得分的路径来更新 dp\[i\]。

解题步骤：

1.  创建一个数组 dp，大小为 n（格子数量），初始化 dp\[0\] = score\[0\]（因为游戏从第一个格子开始）。
2.  对于 dp\[i\]（i从1到n-1），计算从 max(0, i-k) 到 i-1（即前k个可能的格子）中能得到的最大得分加上当前格子的得分 score\[i\]。
3.  最终，dp\[n-1\] 将包含到达最后一个格子时的最大得分。

### 五、Java算法源码 ###

public class Test05 {
        
        /**
         * 每个格子上有特定的分数 score = [1, -1, -6, 7, -17, 7]，
         * 从起点score[0]开始，每次最大的步长为k，请你返回小明跳到终点 score[n-1] 时，能得到的最大得分。
         */
    	public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt(); // 读取格子数量
            int[] score = new int[n];
            for (int i = 0; i < n; i++) {
        
                score[i] = scanner.nextInt(); // 读取每个格子的得分
            }
            int k = scanner.nextInt(); // 读取最大步长
            System.out.println(maxScore(n, score, k)); // 输出最大得分
        }
        
        public static int maxScore(int n, int[] score, int k) {
        
            if (n == 0) return 0;
            int[] dp = new int[n];
            dp[0] = score[0]; // 从第一个格子开始，初始化第一个格子的得分
    
            // 动态规划计算到达每个格子的最大得分
            for (int i = 1; i < n; i++) {
        
                int maxPrevScore = Integer.MIN_VALUE; // 初始化为极小值，寻找最大的得分
                // 计算能跳到当前格子i的前k个格子的最大得分
                for (int j = 1; j <= k; j++) {
        
                    if (i - j >= 0) {
        
                        maxPrevScore = Math.max(maxPrevScore, dp[i - j]);
                    }
                }
                // 更新到达当前格子的最大得分
                dp[i] = score[i] + (maxPrevScore != Integer.MIN_VALUE ? maxPrevScore : 0);
            }
    
            // 最后一个格子的得分就是答案
            return dp[n - 1];
        }
    }

通过动态规划方法计算了在给定步长限制下跳格子游戏的最大得分。通过逐一考虑每个可能的前置位置并选择最优的得分累加方式，确保了每一步都是基于之前得到的最佳结果。这种方法有效地解决了问题，即使在面对较大的 n 和 k 时也能高效运行。

### 六、效果展示 ###

#### 1、输入 ####

6  
1 -1 -6 7 -17 7  
2

#### 2、输出 ####

#### 3、说明 ####

![在这里插入图片描述][d0eb6e26347c4ec1b41b9f597b5a0a61.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/08dc520368aa408597917cd7e4b5f7f7.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[d0eb6e26347c4ec1b41b9f597b5a0a61.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c4f60be38c924535bcf5fff2bee6c4f7.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/bc587c0e80fb4e918b5ea4bfcc5f1435.gif