华为OD机试真题 Java 实现【跳格子2】【2023 B卷 100分】,附详细解题思路-LMLPHP

一、题目描述

小明和朋友玩跳格子游戏,有n个连续格子组成的圆圈,每个格子有不同的分数,小朋友可以选择从任意格子起跳,但是不能跳连续的格子,不能回头跳,也不能超过一圈。

给定一代表每个格子得分的非负整数数组,计算能够得到的最高分数。

二、输入描述

给定一个数组,第一个格子和最后一个格子首尾相连,比如: 2 3 2

三、输出描述

输出能够得到的最高分,比如:3

四、解题思路

动态规划算法将原问题视作若干个重叠子问题的逐层递进,每个子问题的求解过程都构成一个阶段。

在完成前一个阶段的计算之后,动态规划才会进入到下一个阶段的计算。

动态规划算法解决了“子问题重叠性质”问题,子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。

动态规划算法会对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

  1. 因为①数组首尾相连、②不能连续跳,所以要分而治之,采取动态规划算法;
  2. 包含第一个数字,但不包含最后一个数字的为一组;
  3. 不包含第一个数字,但包含最后一个数字的为一组;
  4. 采取动态规划算法,获取两组数据中的最大值;

五、Java算法源码

public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    // 每个格子有不同的分数
    int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    // 一共有多少个格子
    int n = arr.length;

    switch (n){
        case 1:
            System.out.println(arr[0]);
            break;
        case 2:
            System.out.println(Math.max(arr[0],arr[1]));
            break;
        default:
            // 因为①数组首尾相连、②不能连续跳,所以要分而治之,采取动态规划算法
            int[] arr1 = new int[n - 1];
            int[] arr2 = new int[n - 1];

            for (int i = 0; i < n; i++) {
                // 包含第一个数字,但不包含最后一个数字的为一组;
                if (i != n - 1) {
                    arr1[i] = arr[i];
                }

                // 不包含第一个数字,但包含最后一个数字的为一组;
                if (i != 0) {
                    arr2[i - 1] = arr[i];
                }
            }

            // 获取两组数据中的最大值
            System.out.println(Math.max(getMax(arr1), getMax(arr2)));
            break;
    }
}

/**
 * 动态规划
 * 
 * 获取两组数据中的最大值
 */
public static int getMax(int[] nums) {

    int[] dp = new int[nums.length];
    dp[0] = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (i == 1) {
            dp[i] = Math.max(nums[i], dp[i - 1]);
        } else {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
    }

    return dp[nums.length - 1];
}

六、效果展示

1、输入

1 5 2 3 4 1

2、输出

9

3、说明

华为OD机试真题 Java 实现【跳格子2】【2023 B卷 100分】,附详细解题思路-LMLPHP


🏆下一篇:华为OD机试真题 Java 实现【跳房子II】【2023 B卷 100分】,附详细解题思路

🏆本文收录于,华为OD机试(JAVA)(2022&2023)

本专栏包含了最新最全的2023年华为OD机试真题,有详细的分析和Java解答。已帮助1000+同学顺利通过OD机考。专栏会持续更新,每天在线答疑。

华为OD机试真题 Java 实现【跳格子2】【2023 B卷 100分】,附详细解题思路-LMLPHP

06-06 13:48