给定一个长度为n的整型数组，表示一个选手在n轮内可选择的牌面分数。选手基于规则选牌，
请计算所有轮结束后其可以获得的最高总分数。
选择规则如下：
在每轮里选手可以选择获取该轮牌面，则其总分数加上该轮牌面分数，为其新的总分数。 选手也可不选择本轮牌面直接跳到下一轮，此时将当前总分数还原为3轮前的总分数，若当前轮次小于等于3（即在第1、2、3轮选择跳过轮次），则总分数置为0。 选手的初始总分数为0，且必须依次参加每一轮
分数值为整数，-100 <= 分数值 <= 100。
不考虑格式问题
1,-5,-6,4,3,6,-2
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">11
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">你可以选择当前卡牌并获得它的分数。
你也可以跳过当前卡牌，但跳过后，你必须至少跳过 2 张卡牌（即从当前卡牌跳到当前卡牌的下三张）。
任务是计算最大得分。
递归思路： 这道题目可以通过递归来解决。对于当前的卡牌 index，我们有两种选择：
选择当前卡牌： 选择卡牌的得分是当前卡牌的分数加上从 index-1 处计算得到的最大得分。
跳过当前卡牌： 直接跳到 index-3 处，计算从那一位置开始的最大得分。
递归的状态是 get_max_score(arr, index)，其中 arr 是卡牌数组，index 是当前的卡牌位置。
动态规划优化： 由于递归可能会重复计算相同的子问题，因此使用 记忆化递归（Memoization） 来存储已经计算过的结果，避免重复计算，提升效率。
递归终止条件：
如果 index < 0，表示没有卡牌可以选择，返回 0。
如果 index 已经计算过了（即 index 存在于 memo 中），则直接返回 memo[index]。
最终解： 递归的最终结果是从最后一个卡牌开始，计算出最大得分。
# 定义递归函数，计算从第 index 张卡牌开始的最大得分
def get_max_score(arr, index, memo):
# 递归终止条件：如果 index 小于 0，表示没有卡牌可以选择，返回 0
if index < 0:
return 0
# 如果当前 index 的值已经计算过，直接返回记忆化的结果
if index in memo:
return memo[index]
# 选择当前卡牌：取当前卡牌的分数 + 从 index - 1 处继续递归
take = get_max_score(arr, index - 1, memo) + arr[index]
# 跳过当前卡牌：跳到 index - 3 处继续递归
skip = get_max_score(arr, index - 3, memo)
# 取选择当前卡牌和跳过当前卡牌中的最大得分，并保存到 memo 中
memo[index] = max(take, skip)
# 返回当前 index 位置的最大得分
return memo[index]
# 主程序：输入卡牌分数，并计算最大得分
cards = list(map(int, input().split(","))) # 读取输入的卡牌分数并转换为列表
print(get_max_score(cards, len(cards) - 1, {})) # 从最后一张卡牌开始，计算最大得分
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">每次选择卡牌，你可以选择当前卡牌并获得它的分数，或者跳过当前卡牌。
如果选择了当前卡牌，那么下一个选择会从上一个卡牌的下一个卡牌开始（即递归调用 currentRound-1）。
如果跳过当前卡牌，你需要跳过至少 2 张卡牌（即从 currentRound-3 开始计算）。
为了避免重复计算，我们使用 记忆化递归（Memoization），将已经计算过的子问题结果存储在 memo 中。通过使用 memo，可以将时间复杂度优化到 O(n)，从而避免暴力递归中的重复计算。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
// 创建一个 HashMap 来存储已经计算过的子问题结果
private static Map<Integer, Integer> memo = new HashMap<>();
public static void main(String[] args) {
// 创建 Scanner 对象来读取输入
Scanner scanner = new Scanner(System.in);
// 读取输入并将其按逗号分割为字符串数组
String[] input = scanner.nextLine().split(",");
// 将字符串数组转换为整型数组
int[] points = new int[input.length];
for (int i = 0; i < input.length; i++) {
points[i] = Integer.parseInt(input[i]);
}
// 输出从最后一张卡牌开始，计算最大得分
System.out.println(maxScore(points, points.length - 1));
}
// 计算从当前 round 开始能得到的最大得分
private static int maxScore(int[] points, int currentRound) {
// 如果当前 round 小于 0，表示没有卡牌可以选择，返回 0
if (currentRound < 0) {
return 0;
}
// 如果当前 round 的得分已经计算过，直接从 memo 中返回结果
if (memo.containsKey(currentRound)) {
return memo.get(currentRound);
}
// 选择当前卡牌：当前卡牌的分数 + 从 currentRound-1 开始递归计算的最大得分
int choose = points[currentRound] + maxScore(points, currentRound - 1);
// 跳过当前卡牌：跳到 currentRound-3 开始递归计算的最大得分
// 如果 currentRound 小于 3，跳过卡牌就相当于返回 0
int skip = (currentRound < 3) ? 0 : maxScore(points, currentRound - 3);
// 当前 round 的最大得分是选择当前卡牌和跳过当前卡牌两种选择的最大值
int result = Math.max(choose, skip);
// 将结果保存到 memo 中，避免重复计算
memo.put(currentRound, result);
// 返回当前 round 的最大得分
return result;
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">更新中
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">选择当前卡牌： 如果选择当前卡牌，就需要加上当前卡牌的得分，然后递归计算从当前卡牌的前一张开始的最大得分。
跳过当前卡牌： 如果跳过当前卡牌，必须跳过至少 2 张卡牌，即从 currentRound-3 开始递归计算。
为了避免重复计算，我们可以使用 记忆化递归（Memoization） 来存储已经计算过的子问题的结果，从而提升效率。
思路概述：
使用递归函数 maxScore(points, currentRound) 计算从 currentRound 开始到最后一张卡牌的最大得分。
如果当前卡牌已被计算过，则直接从 memo 中获取结果。
对于每张卡牌，有两种选择：选择当前卡牌或者跳过当前卡牌。
将每次计算的结果存入 memo，以避免重复计算，提高效率
'use strict';
// 创建一个 Map 来存储已经计算过的结果（记忆化）
const memo = new Map();
// 递归函数：计算从 currentRound 开始的最大得分
const maxScore = (points, currentRound) => {
// 如果当前回合小于 0，表示没有卡牌可以选择，返回 0
if (currentRound < 0) {
return 0;
}
// 如果当前回合已经计算过结果，直接从 memo 中返回
if (memo.has(currentRound)) {
return memo.get(currentRound);
}
// 选择当前卡牌：当前卡牌得分 + 从 currentRound-1 继续计算最大得分
const choose = points[currentRound] + maxScore(points, currentRound - 1);
// 跳过当前卡牌：跳到 currentRound-3 继续计算最大得分
// 如果 currentRound 小于 3，跳过卡牌就相当于返回 0
const skip = currentRound < 3 ? 0 : maxScore(points, currentRound - 3);
// 当前回合的最大得分是选择当前卡牌和跳过当前卡牌中的最大值
const result = Math.max(choose, skip);
// 将当前回合的最大得分保存到 memo 中
memo.set(currentRound, result);
// 返回当前回合的最大得分
return result;
};
// 主程序：处理输入并调用 maxScore 函数
const main = () => {
// 让 stdin 持续接收输入数据
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
// 接收每次输入的块数据
process.stdin.on('data', (chunk) => {
input += chunk;
});
// 输入结束时调用回调函数
process.stdin.on('end', () => {
// 处理输入，去除两端空格，并按逗号分割，转换为数字数组
const points = input.trim().split(',').map(Number);
// 调用 maxScore 函数，从最后一张卡牌开始，计算最大得分
console.log(maxScore(points, points.length - 1));
});
};
// 执行主函数
main();
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：