【每日一题Day154】LC1626无矛盾的最佳球队 | 动态规划
创始人
2025-06-01 13:14:00
0

无矛盾的最佳球队【LC1626】

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

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

给你两个列表 scoresages,其中每组 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;}}
    

相关内容

热门资讯

国内刷屏!日本化工巨头集体围观... 【DT新材料】获悉,近日, 东粤化学20 万吨/年混合废塑料资源化综合利用示范性项目试生产成功,受到...
华夏红利量化选股股票A:202... AI基金华夏红利量化选股股票A(021570)披露2025年二季报,第二季度基金利润42.66万元,...
西力科技:7月18日融资买入7... 证券之星消息,7月18日,西力科技(688616)融资买入787.74万元,融资偿还548.63万元...
多家银行细化提振消费“路线图”... 本报记者 杨洁 今年以来,一系列扩内需、促消费政策密集出台,市场活力不断激发。《证券日报》记者了解到...
基建概念股早盘走高,基建相关E... 基建概念股早盘走高,中国电建涨停,中国能建涨超9%,中国交建涨超5%。 受重仓股上涨影响,基建相关E...
明星基金经理二季度调仓曝光,多... 2025年二季报逐步披露,多位明星基金经理最新调仓情况浮出水面。 今年以来,创新药板块表现持续亮眼,...
原创 二... “卖房比卖白菜还难”,以前这听着就是个搞笑段子,现在却成了活生生的现实!你瞧瞧,电梯里、楼道间,还有...
兆威机电赴港IPO,近两年半员... 瑞财经 严明会 近日,据港交所,深圳市兆威机电股份有限公司(以下简称“兆威机电”)向港交所提交上市申...
越卖越贵,中产都开始“抢冰块”... 作者:陈澄 编辑:安迪 在经历过雪糕刺客、防晒衣刺客后,许多人发现,今年夏季的新刺客,似乎轮到了冰块...
晨丰科技:向全资子公司北网智算... 晨丰科技晚间公告,公司拟以自有资金9,000万元向全资子公司北网智算进行增资,增资后北网智算的注册资...
科创债发行规模超7600亿元,... 今年央行、中国证监会联合发布关于支持发行科创债有关事宜的公告,旨在通过创新金融工具进一步疏通科技企业...
泰福泵业关联并购:“牛散”家族... 2025年7月9日,主营水泵制造的泰福泵业(300992.SZ)宣布收购浙江南洋华诚科技股份有限公司...
A股特别提示(7-21):英伟... 来源:国金证券第5小时 新股:悍高集团 001221.SZ 1、国资央企援藏再升级。在国资央企助力西...
摩根基金管理(中国)胡迪旗下摩... 证券之星消息,7月21日摩根基金管理(中国)旗下胡迪 何智豪管理的摩根标普港股通低波红利交易型开放式...
争议升级!特朗普起诉《华尔街日... 【环球时报驻美国特约记者 戴润芝 环球时报特约记者 于文】美国总统特朗普18日起诉《华尔街日报》,索...
宋清辉:经常喜欢抛头露面的表演... 宗庆后事件以及其他案例的启示在于,在信息爆炸的时代,任何刻意塑造的“完美人设”都如同沙堡,经不起时间...
贴心服务赢得客户赞誉 本报晋城讯 近年来,阳城农商银行始终坚守金融为民初心,以“我为群众办实事”为行动指南,持续推进金融服...
正裕工业:拟定增募资不超4.5... 正裕工业晚间公告称,公司拟定增募资不超过4.5亿元,扣除发行费用后的净额用于正裕智造园(二期)项目及...
《2024年全国海水利用报告》... 中国日报7月19日电(记者 赵磊)记者从自然资源部获悉,近日,该部海洋战略规划与经济司发布《2024...