【每日一题Day154】LC1626无矛盾的最佳球队 | 动态规划

无矛盾的最佳球队【LC1626】

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

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

给你两个列表

scores

和

ages

，其中每组

scores[i]

和

ages[i]

表示第

i

名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

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

• 思路将球员按照年龄升序排列，年龄相同的按照分数升序排序，假设第 i i i个人是球队中下标最大的，那么对于球队中下标比 i i i小的 j j j，必然有 a g e [ j ] ≤ a g e [ i ] age[j] \le age[i] age[j]≤age[i]- 如果 a g e [ j ] = a g e [ i ] age[j]=age[i] age[j]=age[i]，年龄相同，分数从小到大排序，所以 s c o r e [ j ] ≤ s c o r e [ i ] score[j] \le score[i] score[j]≤score[i]- 如果 a g e [ j ] < a g e [ i ] age[j]<age[i] age[j]<age[i]，按照题目要求，必须满足 s c o r e [ j ] ≤ s c o r e [ i ] score[j] \le score[i] score[j]≤score[i]所以排序后，需要从排序数组中选择score之和最大的递增子序列【允许有相同元素】，与题LC300相同，使用dp解决
• 动态规划排序后的数组记为players， p l a y e r s [ i ] [ 0 ] players[i][0] players[i][0]为年龄， p l a y e r s [ i ] [ 1 ] players[i][1] players[i][1]为分数1. 确定dp数组（dp table）以及下标的含义dp[i]:dp[i]表示i之前包括i的以players[i]结尾最长上升子序列的最大分数之和2. 确定递推公式如果 p l a y e r s [ i ] [ 1 ] ≥ p l a y e s [ j ] [ 1 ] players[i][1] \ge playes[j][1] players[i][1]≥playes[j][1]，那么 d p [ i ] = m a x ( d p [ i ] , d p [ j ] + p l a y e r s [ 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数组classSolution{publicintbestTeamScore(int[] scores,int[] ages){int n = scores.length;int[][] players =newint[n][2];for(int i =0; i < n; i++){ players[i][0]= ages[i]; players[i][1]= scores[i];}Arrays.sort(players,newComparator<int[]>(){publicintcompare(int[] o1,int[] o2){if(o1[0]== o2[0]){return o1[1]- o2[1];}return o1[0]-o2[0];}});int[] dp =newint[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 ( n 2 ) O(n^2) O(n2)- 空间复杂度： O ( n ) O(n) O(n)
• 代码学习：将下标根据值排序classSolution{publicintbestTeamScore(int[] scores,int[] ages){int n = scores.length, ans =0;var ids =newInteger[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 =newint[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背包的感觉，背包的容量为年龄和分数classSolution{int[][] dp;publicintbestTeamScore(int[] scores,int[] ages){int n = scores.length;int[][] players =newint[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 =newint[maxScore +1][maxAge +1];for(int i =0; i <= maxScore; i++){Arrays.fill(dp[i],-1);}Arrays.sort(players,newComparator<int[]>(){publicintcompare(int[] o1,int[] o2){if(o1[0]== o2[0]){return o1[1]- o2[1];}return o1[0]-o2[0];}});returndfs(players,0,0,0);}publicintdfs(int[][] players,int i,int maxScore,int age){if(i == players.length)return0;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;}}