假设你是球队的经理。对于即将到来的锦标赛,你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而,球队中的矛盾会限制球员的发挥,所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员,则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表
scores
和ages
,其中每组scores[i]
和ages[i]
表示第i
名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
原本的思路想复杂了,虽然写的也是动态规划也排序了,用dfs回溯写了一版,每个球员有选或者不选两种可能,记录了小于等于当前年龄的最大分数,如果当前分数大于等于该值,才可以选择,然后超时。于是加记忆化,但是记忆化卡在了一个案例,没空就错了,代码放在下面,有兴趣的友友可以看看,也许思路就不大对吧
思路
将球员按照年龄升序排列,年龄相同的按照分数升序排序,假设第iii个人是球队中下标最大的,那么对于球队中下标比iii小的jjj,必然有age[j]≤age[i]age[j] \le age[i]age[j]≤age[i]
所以排序后,需要从排序数组中选择score之和最大的递增子序列【允许有相同元素】,与题LC300相同,使用dp解决
动态规划
排序后的数组记为players
,players[i][0]players[i][0]players[i][0]为年龄,players[i][1]players[i][1]players[i][1]为分数
确定dp数组(dp table)以及下标的含义
dp[i]:dp[i]表示i之前包括i的以players[i]结尾最长上升子序列的最大分数之和
确定递推公式
如果players[i][1]≥playes[j][1]players[i][1] \ge playes[j][1]players[i][1]≥playes[j][1],那么
dp[i]=max(dp[i],dp[j]+players[i][1])dp[i] = max(dp[i], dp[j] + players[i][1]) dp[i]=max(dp[i],dp[j]+players[i][1])
dp数组如何初始化
dp[0]=0;
确定遍历顺序
从前往后遍历
举例推导dp数组
class Solution {public int bestTeamScore(int[] scores, int[] ages) {int n = scores.length;int[][] players = new int[n][2];for (int i = 0; i < n; i++){players[i][0] = ages[i];players[i][1] = scores[i];}Arrays.sort(players, new Comparator(){public int compare(int[] o1, int[] o2){if (o1[0] == o2[0]){return o1[1] - o2[1];}return o1[0] -o2[0];}});int[] dp = new int[n + 1];int res = 0;for (int i = 1; i <= n; i++){for (int j = 0; j < i; j++){if (j == 0 || players[i - 1][1] >= players[j - 1][1]){dp[i] = Math.max(players[i - 1][1] + dp[j], dp[i]);}}res = Math.max(res, dp[i]);}return res;}}
复杂度
代码学习:
将下标根据值排序
class Solution {public int bestTeamScore(int[] scores, int[] ages) {int n = scores.length, ans = 0;var ids = new Integer[n];for (int i = 0; i < n; ++i)ids[i] = i;Arrays.sort(ids, (i, j) -> scores[i] != scores[j] ? scores[i] - scores[j] : ages[i] - ages[j]);var f = new int[n + 1];for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j)if (ages[ids[j]] <= ages[ids[i]])f[i] = Math.max(f[i], f[j]);f[i] += scores[ids[i]];ans = Math.max(ans, f[i]);}return ans;}
}作者:灵茶山艾府
链接:https://leetcode.cn/problems/best-team-with-no-conflicts/solutions/2183029/zui-chang-di-zeng-zi-xu-lie-cong-on2-dao-ojqu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
回溯 错误代码
有点01背包的感觉,背包的容量为年龄和分数
class Solution {int[][] dp;public int bestTeamScore(int[] scores, int[] ages) {int n = scores.length;int[][] players = new int[n][2];int maxScore = 0;int maxAge = 0;for (int i = 0; i < n; i++){maxAge = Math.max(maxAge, ages[i]);maxScore = Math.max(maxScore, scores[i]);players[i][0] = ages[i];players[i][1] = scores[i];}dp = new int[maxScore + 1][maxAge + 1];for (int i = 0; i <= maxScore; i++){Arrays.fill(dp[i], -1);}Arrays.sort(players, new Comparator(){public int compare(int[] o1, int[] o2){if (o1[0] == o2[0]){return o1[1] - o2[1];}return o1[0] -o2[0];}});return dfs(players, 0, 0, 0);}public int dfs(int[][] players, int i, int maxScore, int age){if (i == players.length) return 0;if (maxScore > 0 && age > 0 && dp[maxScore][age] != -1) return dp[maxScore][age];// 不选int score = dfs(players, i + 1, maxScore, age);// 选 if (age == players[i][0] || (age < players[i][0] && players[i][1] >= maxScore)){int curScore = maxScore;int curAge = age;if (curScore <= players[i][1]){curScore = players[i][1];curAge = players[i][0]; }score = Math.max(score, players[i][1] + dfs(players, i + 1, curScore, curAge));}dp[maxScore][age] = score;return score;}}