华为od 跳格子2 java

题目描述

小明和朋友玩跳格子游戏,有 n 个连续格子组成的圆圈,每个格子有不同的分数,小朋友可以选择以任意格子起跳,但是不能跳连续的格子,不能回头跳,也不能超过一圈;给定一个代表每个格子得分的非负整数数组,计算能够得到的最高分数。

输入描述

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

输出描述

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

题意:

1.不能跳连续的格子, 但是可以跳隔了多个的格子。比如 4 1 2 7 2 , 跳 4 2 2 得8分, 跳 4 7 得11分 !!!

2.首尾不能都跳,将序列分为两组, 一组包含第一个元素不包含最后一个元素;另一组不包含第一个元素但包含最后一个元素。分别进行推导,取两者的最大值

3.动态规划


import java.util.*;

//跳格子2

/**
   dp[]数组含义: 表示 最多跳到当前格子的最高分数 (可以不跳到当前格子)。
    递推公式:
    dp[i] =Math.max(dp[i-1], dp[i-2]+nums.get(i));   表示 不跳当前格子即 最多跳到前一个格子的最高分数, 比较 i-2格子的最高分数+当前格子的分数
 */
public class Main{
    // 通用 split 函数,空格切分
    public static List<Integer> split(String input) {
        List<Integer> res = new ArrayList<>();
        for (String s : input.trim().split(" ")) {
            res.add(Integer.parseInt(s));
        }
        return res;
    }

    // 计算不包含首/尾元素时的最大收益(不能相邻)
    public static int calMaxValue(List<Integer> nums) {
        int n = nums.size();
        int[] dp = new int[n];
        //初始化 dp[0],等于第一个格子的分数
        dp[0]=nums.get(0);


        for (int i = 1; i < n; i++) {
            //当i=1,表示 最多跳到第二个格子的最高分数。此时只有两个格子,要么跳第一格要么跳第二格,选分数最高的
            if (i==1){
                dp[i] =Math.max(dp[0], nums.get(i));
            }else {
                dp[i] =Math.max(dp[i-1], dp[i-2]+nums.get(i));

            }
        }
        //返回值表示 最多跳到第n个格子(下标是从0开始的),的最高总分数
        return dp[n-1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        List<Integer> nums = split(input);
        int n = nums.size();

        if (n == 1) {
            System.out.println(nums.get(0));
            return;
        }

        // 不包含尾部元素
        List<Integer> sub1 = nums.subList(0, n - 1);
        // 不包含首元素
        List<Integer> sub2 = nums.subList(1, n);
        // 取较大值
        int res = Math.max(calMaxValue(sub1), calMaxValue(sub2));
        System.out.println(res);
    }
}


全部评论

相关推荐

评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务