华为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); } }