【华为OD-E卷 - 跳格子2 100分（python、java、c++、js、c）】
【华为OD-E卷 - 跳格子2 100分（python、java、c++、js、c）】
题目
小明和朋友玩跳格子游戏，有 n 个连续格子组成的圆圈，每个格子有不同的分数，小朋友可以选择以任意格子起跳，但是不能跳连续的格子，不能回头跳，也不能超过一圈;
给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数
输入描述
- 给定一个数例，第一个格子和最后一个格子首尾相连，如: 2 3 2
输出描述
- 输出能够得到的最高分，如: 3
备注
- 1 ≤ nums.length ≤ 100 1 ≤ nums[i] ≤ 1000
用例
用例一：
输入：
2 3 2
输出：
3
用例二：
输入：
1 2 3 1
输出：
4
python解法
- 解题思路：
# 读取输入数据，将其转换为整数列表
vals = list(map(int, input().split()))
# 计算线性数组的最大不相邻子序列和
def max_points(arr):
n = len(arr)
# 如果数组只有一个元素，直接返回它
if n == 1:
return arr[0]
# 初始化 dp 数组
p = [0] * n
# 只有一个元素时，最大值就是该元素
p[0] = arr[0]
# 如果有两个元素，取较大的那个
if n > 1:
p[1] = max(arr[0], arr[1])
# 动态规划填充数组
for i in range(2, n):
# 核心转移方程：当前最优解 = max(不选当前元素, 选当前元素)
p[i] = max(p[i-1], p[i-2] + arr[i])
# 返回最后一个位置的最大值，即最终结果
return p[-1]
# 计算环形数组的最大不相邻子序列和
def find_max():
# 如果数组只有一个元素，直接返回它
if len(vals) == 1:
return vals[0]
# 取两种情况的最大值
return max(max_points(vals[:-1]), max_points(vals[1:]))
# 输出最终结果
print(find_max())
java解法
- 解题思路
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取输入，使用空格分隔字符串，并转换为整数数组
String[] input = sc.nextLine().split(" ");
int[] vals = new int[input.length];
for (int i = 0; i < input.length; i++) {
vals[i] = Integer.parseInt(input[i]);
}
// 计算并输出最大得分
System.out.println(findMax(vals));
}
// 计算线性数组的最大不相邻子序列和
public static int maxPoints(int[] arr) {
int n = arr.length;
// 只有一个元素，直接返回它
if (n == 1) {
return arr[0];
}
// 动态规划数组
int[] p = new int[n];
// 初始状态
p[0] = arr[0];
// 只有两个元素时，取较大的
if (n > 1) {
p[1] = Math.max(arr[0], arr[1]);
}
// 递推填充动态规划数组
for (int i = 2; i < n; i++) {
p[i] = Math.max(p[i - 1], p[i - 2] + arr[i]);
}
// 返回最后一个位置的最大值
return p[n - 1];
}
// 计算环形数组的最大不相邻子序列和
public static int findMax(int[] vals) {
int n = vals.length;
// 如果数组只有一个元素，直接返回它
if (n == 1) {
return vals[0];
}
// 创建两个新的数组：
// 1. vals1 代表去掉最后一个元素的子数组
// 2. vals2 代表去掉第一个元素的子数组
int[] vals1 = new int[n - 1];
int[] vals2 = new int[n - 1];
// 复制 vals[0] 到 vals[n-2] 形成 vals1
System.arraycopy(vals, 0, vals1, 0, n - 1);
// 复制 vals[1] 到 vals[n-1] 形成 vals2
System.arraycopy(vals, 1, vals2, 0, n - 1);
// 取两个子数组的最大得分
return Math.max(maxPoints(vals1), maxPoints(vals2));
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 监听标准输入，读取一行数据
rl.on("line", (line) => {
// 将输入字符串拆分成整数数组
const nums = line.split(" ").map(Number);
// 计算最大得分并输出
console.log(computeMaxScore(nums));
});
/**
* 计算环形数组的最大不相邻子序列和
* @param {number[]} nums 输入的环形数组
* @returns {number} 最大得分
*/
function computeMaxScore(nums) {
const n = nums.length;
// 如果数组只有一个元素，直接返回它
if (n === 1) return nums[0];
// 计算去掉最后一个元素 和 去掉第一个元素 两种情况的最大值
return Math.max(calcMax(nums.slice(0, -1)), calcMax(nums.slice(1)));
}
/**
* 计算线性数组的最大不相邻子序列和（递归+记忆化）
* @param {number[]} arr 线性数组
* @returns {number} 最大得分
*/
function calcMax(arr) {
// 创建 memo 数组用于记忆化，初始值为 -1，表示未计算
const memo = new Array(arr.length).fill(-1);
// 调用递归计算最大得分
return maxWithMemo(arr, arr.length - 1, memo);
}
/**
* 递归计算最大得分，使用记忆化优化
* @param {number[]} arr 线性数组
* @param {number} i 当前索引
* @param {number[]} memo 记忆化数组
* @returns {number} 计算到 i 位置的最大得分
*/
function maxWithMemo(arr, i, memo) {
// 边界情况：索引小于 0，返回 0（无贡献）
if (i < 0) return 0;
// 如果 memo[i] 已经计算过，直接返回
if (memo[i] !== -1) return memo[i];
// 计算当前索引的最优解，并存入 memo 数组
memo[i] = Math.max(
maxWithMemo(arr, i - 1, memo), // 不取 arr[i]，继承之前的最大值
maxWithMemo(arr, i - 2, memo) + arr[i] // 取 arr[i]，但必须跳过 arr[i-1]
);
return memo[i];
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏