【華為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] 形成 vals1System.arraycopy(vals, 0, vals1, 0, n - 1);// 復制 vals[1] 到 vals[n-1] 形成 vals2System.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];
}

注意：

如果發現代碼有用例覆蓋不到的情況，歡迎反饋！會在第一時間修正，更新。
解題不易，如對您有幫助，歡迎點贊/收藏