1626. 无矛盾的最佳球队

题目链接：1626. 无矛盾的最佳球队

方法一：子集型回溯 + 记忆化

解题思路

1. 先对\(scores\)和\(ages\)数组进行预处理得到\(pair<int, int> a[n]\)数组，\(a[i].first = score[i], a[i].second = ages[i]\)，然后进行\(sort\)排序；
2. 枚举计算\([i, n - 1]\)区间的最大分数\(score_i\) \(= dfs(i)，i = 0, 1, ..., n - 1\)。\(ans = max(score_i)\)。
3. \(dfs(i)\)：\(curScore = a[i].first\)，以\(i\)为起点，在\([i + 1, n - 1]\)中找所有满足条件a[i].second <= a[j].second的\(j\)，即找没有矛盾的的队员，\(curScore = max(dfs(j) + a[i].first, curScore)\)，return curScore。

代码

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size(), ans = 0;
        pair<int, int> a[n];
        for (int i = 0; i < n; i ++ ) a[i] = {scores[i], ages[i]};
        sort(a, a + n);
        int cache[n]; memset(cache, -1, sizeof(cache));
        function<int(int)> dfs = [&](int i) -> int {
            int curScore = a[i].first;
            if (cache[i] != -1) return cache[i];
            for (int j = i + 1; j < n; j ++ ) {
                if (a[j].second >= a[i].second) {
                    curScore = max(curScore, dfs(j) + a[i].first);
                }
            }
            cache[i] = curScore;
            return curScore;
        };
        for (int i = 0; i < n; i ++ ) {
            ans = max(ans, dfs(i));
        }
        return ans;
    }
};

方法二：动态规划

解题思路

改写上方思路为动态规划：

1. \(cache\)数组改为\(f\)数组；
2. 递归改为循环。递归过程中是在起点的右边找不矛盾的队友，然后在向右递归；循环则是对应归的过程，即 \(i = n - 1 => 0\)，\(f[i] = a[i].first\)，然后在\(i\)的右边\([i + 1, n - 1]\)中找不矛盾的\(j\)，\(f[i] = max(f[i], f[j] + a[i].first)\)；
3. \(ans = max(f)\)。

代码

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size(), ans = 0;
        pair<int, int> a[n];
        for (int i = 0; i < n; i ++ ) a[i] = {scores[i], ages[i]};
        sort(a, a + n);
        int f[n]; memset(f, 0, sizeof(f));
        for (int i = n - 1; i >= 0; i -- ) {
            f[i] = a[i].first;
            for (int j = i; j < n; j ++ ) {
                if (a[j].second >= a[i].second) {
                    f[i] = max(f[i], f[j] + a[i].first);
                }
            }
            ans = max(ans, f[i]);    
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n^2)\)；
空间复杂度：\(O(n)\)。