无矛盾的最佳球队【LC1626】

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

原本的思路想复杂了，虽然写的也是动态规划也排序了，用dfs回溯写了一版，每个球员有选或者不选两种可能，记录了小于等于当前年龄的最大分数，如果当前分数大于等于该值，才可以选择，然后超时。于是加记忆化，但是记忆化卡在了一个案例，没空就错了，代码放在下面，有兴趣的友友可以看看，也许思路就不大对吧

• 思路

  将球员按照年龄升序排列，年龄相同的按照分数升序排序，假设第iii个人是球队中下标最大的，那么对于球队中下标比iii小的jjj，必然有age[j]≤age[i]age[j] \le age[i]age[j]≤age[i]

  • 如果age[j]=age[i]age[j]=age[i]age[j]=age[i]，年龄相同，分数从小到大排序，所以score[j]≤score[i]score[j] \le score[i]score[j]≤score[i]
  • 如果age[j]

  所以排序后，需要从排序数组中选择score之和最大的递增子序列【允许有相同元素】，与题LC300相同，使用dp解决

• 动态规划

  排序后的数组记为players，players[i][0]players[i][0]players[i][0]为年龄，players[i][1]players[i][1]players[i][1]为分数

  1. 确定dp数组（dp table）以及下标的含义

     dp[i]:dp[i]表示i之前包括i的以players[i]结尾最长上升子序列的最大分数之和

  2. 确定递推公式

     如果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])

  3. dp数组如何初始化

     dp[0]=0;

  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(){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;}}
  

  • 复杂度

    • 时间复杂度：O(n2)O(n^2)O(n2)
    • 空间复杂度：O(n)O(n)O(n)

• 代码学习：

  将下标根据值排序

  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;}}