推荐|【华为OD-E卷 -68 玩牌高手 100分（python、java、c++、js、c）】

【华为OD-E卷 - 玩牌高手 100分（python、java、c++、js、c）】

题目

给定一个长度为n的整型数组，表示一个选手在n轮内可选择的牌面分数。选手基于规则选牌，
请计算所有轮结束后其可以获得的最高总分数。
选择规则如下：
在每轮里选手可以选择获取该轮牌面，则其总分数加上该轮牌面分数，为其新的总分数。选手也可不选择本轮牌面直接跳到下一轮，此时将当前总分数还原为3轮前的总分数，若当前轮次小于等于3（即在第1、2、3轮选择跳过轮次），则总分数置为0。选手的初始总分数为0，且必须依次参加每一轮

输入描述

第一行为一个小写逗号分割的字符串，表示n轮的牌面分数，1<= n <=20。

分数值为整数，-100 <= 分数值 <= 100。

不考虑格式问题

输出描述

所有轮结束后选手获得的最高总分数

用例

用例一：

输入：

1,-5,-6,4,3,6,-2

输出：

python解法

解题思路：
问题分析：题目要求从一组卡牌中选择卡牌来获取最大得分，每次选择卡牌时，你可以选择当前卡牌或跳过几张卡牌。具体的规则是：

你可以选择当前卡牌并获得它的分数。
你也可以跳过当前卡牌，但跳过后，你必须至少跳过 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, {}))  # 从最后一张卡牌开始，计算最大得分

java解法

解题思路
这道题目要求从一组卡牌分数中选择卡牌来获得最大得分，每次选择时，你可以选择当前卡牌或者跳过一些卡牌。具体的规则是：

每次选择卡牌，你可以选择当前卡牌并获得它的分数，或者跳过当前卡牌。
如果选择了当前卡牌，那么下一个选择会从上一个卡牌的下一个卡牌开始（即递归调用 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;
    }
}

C++解法

解题思路

更新中

C解法

解题思路

更新中

JS解法

解题思路
本题的目标是从给定的卡牌分数数组中选择卡牌，使得选择的卡牌总得分最大。每次选择卡牌时，有两个选择：

选择当前卡牌：如果选择当前卡牌，就需要加上当前卡牌的得分，然后递归计算从当前卡牌的前一张开始的最大得分。
跳过当前卡牌：如果跳过当前卡牌，必须跳过至少 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();

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏