【华为OD题库-036】跳格子2-java

题目

小明和朋友玩跳格子游戏，有n个连续格子组成的圆圈，每个格子有不同的分数，小朋友可以选择从任意格子起跳，但是不能跳连续的格子，不能回头跳，也不能超过一圈:给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。
输入描述
给定一个数例，第一个格子和最后一个格子收尾相连，如: 2 3 2
输出描述
输出能够得到的最高分，如: 3
说明
1 <= nums.length <= 100
0 <= nums[] <= 1000
示例1:
输入
2 3 2
输出
说明只能跳3这个格子，因为第一个格子和第三个格子收尾相连
示例2
输入
1 2 3 1
输出
4
说明
1+3=4

思路

先不考虑首尾限制，原题转化为，在一个数组中，找到非连续的格子组合，使其得分最大。
可以考虑动态规划解决。以数据为例：94 40 49 65 10
定义dp[i]代表，在前i个数据时，满足条件的最高分数
初始值：
dp[0]代表只有一个数据，得分应该为nums[0]
dp[1]代表在前两个数据跳，不能相邻，所以dp[1]=max(nums[0],nums[1])
对于i>1的情况，dp[i]分两种情况，取当前值和不取当前值；
如果取当前值，那么最大值为：dp[i-2]+nums[i]
如果不取当前值，那么最大值为：dp[i-1]
dp[i]应该为两者的较大值，即dp[i]=max(dp[i-2]+nums[i]，dp[i-1])
从上面的结果来看，我们只关心当前值的上一个值和上上个值，可以使用两个变量来代替dp。
现在考虑首尾限制，可以分为一下两种情况：

1. 选了第一个就不能选择最后一个
2. 不选第一个则可以选择最后一个

分别按照不考虑的逻辑计算上面两种情况的结果，然后取较大结果即可。

题解

package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class JumpCell {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(jumpCell(nums));
    }

    private static int jumpCell(int[] nums) {
        int length = nums.length;
        if(length==1) return nums[0];
        if(length==2) return Math.max(nums[0], nums[1]);
        return Math.max(jumpCellRange(nums, 0, length - 2), jumpCellRange(nums, 1, length - 1));
    }

    private static int jumpCellRange(int[] nums, int start, int end) {
        int before = nums[start], after = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = after;
            after = Math.max(before + nums[i], after);
            before = temp;
        }
        return after;
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。