无矛盾的最佳球队【LC1626】
假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表
scores和ages，其中每组scores[i]和ages[i]表示第i名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
原本的思路想复杂了，虽然写的也是动态规划也排序了，用dfs回溯写了一版，每个球员有选或者不选两种可能，记录了小于等于当前年龄的最大分数，如果当前分数大于等于该值，才可以选择，然后超时。于是加记忆化，但是记忆化卡在了一个案例，没空就错了，代码放在下面，有兴趣的友友可以看看，也许思路就不大对吧
- 思路
4.确定遍历顺序
从前往后遍历
5.举例推导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<int[]>(){ 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<int[]>(){ 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; } }
