Medium

题目描述

你是一支篮球队的经理。对于即将到来的锦标赛，你想要选择总得分最高的球队。球队的得分是球队中所有球员得分的总和。

然而，篮球队不允许有冲突。如果一个年轻球员的得分严格高于一个年长球员的得分，就会产生冲突。相同年龄的球员之间不会产生冲突。

给定两个列表 scores 和 ages，其中 scores[i] 和 ages[i] 分别表示第 i 个球员的得分和年龄，返回所有可能的篮球队中最高的总得分。

示例 1：

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选择所有的球员。

示例 2：

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最好选择后 3 个球员。注意，你可以选择多个相同年龄的球员。

示例 3：

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最好选择前 3 个球员。

约束条件：

  • 1 <= scores.length, ages.length <= 1000
  • scores.length == ages.length
  • 1 <= scores[i] <= 10^6
  • 1 <= ages[i] <= 1000

解题思路

这是一道经典的动态规划问题，核心思想是通过合理的排序来简化冲突判断。

解题思路：

  1. 排序策略：首先按年龄升序排序，年龄相同时按得分升序排序。这样排序后，我们只需要保证后选的球员得分不低于前面已选球员的得分即可。

  2. 状态定义：设 dp[i] 表示以第 i 个球员为最后一个球员时能获得的最大得分。

  3. 状态转移：对于每个球员 i，我们有两种选择：

    • 不选择球员 i：继续考虑下一个球员
    • 选择球员 i：需要在前面所有得分不超过 scores[i] 的球员中找到最优组合

  4. 转移方程：dp[i] = max(dp[j]) + scores[i]，其中 j < i 且 scores[j] <= scores[i]

优化思路：

  • 可以使用树状数组或线段树优化查询过程，但对于本题数据规模，暴力DP已足够
  • 也可以考虑最长递增子序列的变形思路

推荐解法： 排序 + 动态规划，时间复杂度合理且实现简洁。

代码实现

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<pair<int, int>> players;
        
        // 按年龄排序，年龄相同时按得分排序
        for (int i = 0; i < n; i++) {
            players.push_back({ages[i], scores[i]});
        }
        sort(players.begin(), players.end());
        
        vector<int> dp(n, 0);
        int maxScore = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = players[i].second; // 只选择当前球员
            
            // 尝试与之前的球员组合
            for (int j = 0; j < i; j++) {
                if (players[j].second <= players[i].second) {
                    dp[i] = max(dp[i], dp[j] + players[i].second);
                }
            }
            
            maxScore = max(maxScore, dp[i]);
        }
        
        return maxScore;
    }
};

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        n = len(scores)
        # 按年龄排序，年龄相同时按得分排序
        players = sorted(zip(ages, scores))
        
        dp = [0] * n
        max_score = 0
        
        for i in range(n):
            dp[i] = players[i][1]  # 只选择当前球员
            
            # 尝试与之前的球员组合
            for j in range(i):
                if players[j][1] <= players[i][1]:
                    dp[i] = max(dp[i], dp[j] + players[i][1])
            
            max_score = max(max_score, dp[i])
        
        return max_score

public class Solution {
    public int BestTeamScore(int[] scores, int[] ages) {
        int n = scores.Length;
        var players = new List<(int age, int score)>();
        
        // 按年龄排序，年龄相同时按得分排序
        for (int i = 0; i < n; i++) {
            players.Add((ages[i], scores[i]));
        }
        players.Sort();
        
        int[] dp = new int[n];
        int maxScore = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = players[i].score; // 只选择当前球员
            
            // 尝试与之前的球员组合
            for (int j = 0; j < i; j++) {
                if (players[j].score <= players[i].score) {
                    dp[i] = Math.Max(dp[i], dp[j] + players[i].score);
                }
            }
            
            maxScore = Math.Max(maxScore, dp[i]);
        }
        
        return maxScore;
    }
}

var bestTeamScore = function(scores, ages) {
    const n = scores.length;
    const players = [];
    
    // 按年龄排序，年龄相同时按得分排序
    for (let i = 0; i < n; i++) {
        players.push([ages[i], scores[i]]);
    }
    players.sort((a, b) => a[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：排序需要 O(n log n)，动态规划需要 O(n²)，总体为 O(n²)
  • 空间复杂度：需要 O(n) 的空间存储 dp 数组和排序后的球员信息