题目链接：1626. 无矛盾的最佳球队
方法一：子集型回溯 + 记忆化
解题思路
- 先对\(scores\)和\(ages\)数组进行预处理得到\(pair<int, int> a[n]\)数组，\(a[i].first = score[i], a[i].second = ages[i]\)，然后进行\(sort\)排序；
- 枚举计算\([i, n - 1]\)区间的最大分数\(score_i\) \(= dfs(i)，i = 0, 1, ..., n - 1\)。\(ans = max(score_i)\)。
- \(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;
}
};
方法二：动态规划
解题思路
改写上方思路为动态规划：
- \(cache\)数组改为\(f\)数组；
- 递归改为循环。递归过程中是在起点的右边找不矛盾的队友，然后在向右递归；循环则是对应归的过程，即 \(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)\)；
- \(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)\)。