动态规划与离散化：解决LeetCode 1626双约束优化问题-北京尧图网络

1. 项目概述从一道“棘手”的面试题说起最近在带团队刷题和准备技术面试时LeetCode 1626 “无矛盾的最佳球队”这道题反复被提及。很多有经验的C开发者初次接触时也会觉得它比普通的动态规划DP问题要“绕”一些。问题本身描述很生活化你是一支球队的经理有一份球员名单每个球员有年龄和分数两个属性。你需要组建一支“无矛盾”的球队即球队中不能有年轻球员分数严格高于年长球员的情况这模拟了资历与贡献的潜在冲突。目标是使得球队所有球员的分数总和最大。这听起来像是个排序加贪心或者简单DP的问题但当你动手实现时会发现直接定义状态dp[i]为考虑前i个球员时的最大分数和会遇到麻烦。因为“无矛盾”这个条件不是仅仅关于相邻球员而是关于球队中任意两个球员的。这迫使我们必须将年龄和分数这两个维度同时纳入状态考量。最直观的二维DP思路即dp[a][s]表示处理到某个年龄、某个分数时的最大得分和其空间开销会大到无法承受年龄和分数范围都可能上万。这就是这道题的核心难点也是其价值所在——它逼着你必须使用离散化这一关键技术与动态规划结合将看似不可解的问题优化到可接受的范围。本文将带你深入这道题的骨髓。我不会仅仅给出AC代码而是会拆解整个思考链路为什么二维DP是自然的思路但不可行离散化如何巧妙地压缩状态空间在C中实现离散化有哪些工程细节和陷阱最后我们如何将离散化后的坐标映射回DP状态转移方程通过这道题你收获的将不仅是一个解法而是处理“双约束条件优化问题”的一种通用思维框架和C实现技巧。无论你是正在备战面试还是希望深化对DP与离散化结合的理解这篇来自一线的实战解析都能给你带来实实在在的收获。2. 问题核心与暴力DP的困局2.1 深入理解“无矛盾”条件首先我们必须把问题翻译成更精确的数学模型。给定两个长度相等的数组scores和ages我们需要找到一个下标集合使得对于集合中的任意两个下标i和j如果ages[i] ages[j]那么必须有scores[i] scores[j]。在这个约束下最大化sum(scores[i])。这个条件等价于在我们选出的球员序列中年龄和分数必须同时是非递减的。注意这里允许年龄相等也允许分数相等。这一点很关键它意味着我们可以先对球员进行排序将双变量问题转化为单变量问题上的约束。一个常见的预处理策略是将球员按照年龄升序排序如果年龄相同则按分数升序排序。排序后“无矛盾”条件就简化为了在排序后的序列中我们选取一个子序列要求这个子序列的分数也是非递减的。因为年龄已经排好序了我们只需要保证选出来的球员其分数值不随着索引增加而减少即可。这立刻让我们联想到了经典的**最长递增子序列LIS**问题及其变种。只不过LIS要求严格递增而这里要求非递减并且我们的目标不是序列最长而是分数和最大。2.2 从LIS模型到二维DP的必然性既然联想到了LIS那么最直接的DP思路就呼之欲出了。定义dp[i]为以第i个球员排序后作为球队中最后一名球员时所能获得的最大分数总和。那么状态转移方程呢为了将球员i加入球队我们需要找到之前的一个球员j(j i)满足scores[j] scores[i]以保证分数非递减。然后dp[i]就可以从dp[j] scores[i]转移而来。同时球员i也可以独自组成一支球队即dp[i]至少为scores[i]。因此转移方程为dp[i] max(scores[i], max_{j i 且 score[j] score[i]} {dp[j] scores[i]})最终答案就是所有dp[i]中的最大值。这个思路的时间复杂度是 O(n²)对于n最大为1000的题目限制来说是完全可以接受的1000*10001e6次操作。实际上这就是本题的基础解法。很多人在思考时走到这一步就觉得问题解决了。注意这里有一个非常重要的实现细节。排序时如果年龄相同为什么建议按分数升序排考虑两个年龄相同的球员A(分数5)和B(分数3)。如果先排A后排B当我们处理B时寻找j满足score[j] score[B]3此时A的分数53不符合条件B无法接在A后面。但年龄相同的球员之间其实不应该有“顺序”导致的矛盾他们可以同时存在于球队中。按分数升序排序后在处理分数较小的球员时他看不到后面分数更大的同龄人避免了本不该存在的转移限制。这是一个排序技巧用于处理等值情况。2.3 二维DP的诱惑与维度灾难上述一维DP是可行的但它真的是最本质的模型吗我们回过头看“无矛盾”条件年龄和分数都需非递减。这本质上是一个二维偏序问题。更本质的DP状态定义应该是dp[a][s]表示我们考虑所有年龄不超过a且分数不超过s的球员时能组成的无矛盾球队的最大分数和。如果这个状态定义可行那么转移会非常直观当我们遇到一个年龄为age分数为score的球员时我们可以选择不选他则dp[age][score] dp[age-1][score]假设年龄是离散整数或者选择他那么球队在选他之前最后一名球员的年龄和分数都不能超过他即dp[age][score] dp[age][score]与dp[age][score] score的较大值等等这里有点乱。更准确地说选择当前球员(a, s)后新的状态dp[a][s]应该由之前所有满足a a且s s的状态dp[a][s]加上s转移而来并取最大值。同时状态本身具有传递性dp[a][s]也应该继承dp[a-1][s]和dp[a][s-1]的最大值即不考虑当前分数或年龄上限的球员。这种思路的终极形态其实是一个基于二维前缀和的动态规划。其状态转移方程可以构思为dp[i][j] max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] (if player exists at (i,j) then score else 0))但这需要我们将年龄和分数映射到连续的整数索引上并且dp矩阵的每一个点(i, j)都代表一个“年龄为i分数为j”的虚拟球员是否存在。这显然是不现实的。困局所在年龄和分数的取值范围可能非常大题目中均可达 10^6。如果直接开辟dp[10^61][10^61]的数组无论是内存约 10^12 字节太庞大了还是时间复杂度都是不可能的。这就是二维DP思路直接碰壁的地方。然而这个二维模型更贴近问题的本质结构。我们需要的是一种方法既能保留这种二维关系的逻辑又能将巨大的坐标范围“压缩”到可控的规模。这个方法就是离散化。3. 离散化化无穷为有穷的关键技术3.1 离散化究竟解决了什么问题离散化是一种非常经典的技巧常用于处理定义域很大但实际有效值点很少的情况。其核心思想是只关心值的相对大小关系而不关心其绝对数值。在我们的问题中年龄和分数的具体值比如25岁还是26岁1000分还是1001分本身不重要重要的是球员之间年龄谁大谁小分数谁高谁低。例如有三个球员年龄为{1, 100, 10000}在比较时我们只需要知道第一个最小第二个中间第三个最大。我们可以用{0, 1, 2}来映射它们而不影响大小关系。同样对于分数也是如此。这样做的好处是巨大的。假设有n个球员那么年龄和分数这两个维度各自最多只有n个不同的值。通过离散化我们可以将每个维度的坐标范围从原来的 [1, 10^6] 压缩到 [0, n-1]。那么一个潜在的二维状态空间dp[a][s]的大小就从10^6 * 10^6降到了n * n。对于n 1000n*n 1e6个状态这在时间和空间上就都是可处理的了。3.2 C中的离散化标准实现与细节在C中离散化通常借助std::vector和std::sort、std::unique、std::lower_bound这几个标准算法来完成。下面我们以对分数进行离散化为例拆解每一步步骤1收集所有需要离散化的值vectorint all_scores(scores.begin(), scores.end());这里我们创建了一个包含所有分数值的副本。注意通常我们会把年龄也做同样的处理但在这个问题里有一个更优的策略。步骤2排序并去重sort(all_scores.begin(), all_scores.end()); all_scores.erase(unique(all_scores.begin(), all_scores.end()), all_scores.end());std::sort将序列排序。std::unique将相邻的重复元素“移动”到容器末尾并返回指向去重后新逻辑末尾的迭代器。我们再用erase方法将重复的元素物理删除。现在all_scores就是一个有序且无重复的数组它包含了所有分数值从小到大排序的结果。步骤3建立映射关系将原值映射到离散化后的索引unordered_mapint, int score_to_idx; for (int i 0; i all_scores.size(); i) { score_to_idx[all_scores[i]] i; } // 或者更高效地在需要时将原值转换为索引 int get_index(int val, const vectorint vec) { return lower_bound(vec.begin(), vec.end(), val) - vec.begin(); }通常我们使用第二种方法即不显式创建映射表而是在需要时用std::lower_bound在排序好的all_scores中查找第一个不小于val的位置这个位置差就是离散化后的索引。因为lower_bound在有序数组上的时间复杂度是 O(log n)非常高效。实操心得对于本题有一个关键优化点。我们最终需要的是二维状态dp[age_idx][score_idx]。如果对年龄和分数都进行离散化我们需要一个n * n的DP表。但我们可以做得更好。观察发现当我们对球员按年龄排序后在状态转移时“年龄”维度其实已经通过遍历顺序隐含了。我们只需要一个以离散化分数为索引的一维DP数组再结合年龄排序就可以模拟二维DP的过程。具体来说我们可以用dp[s]表示在所有已考虑的、年龄不超过当前年龄的球员中以分数值离散化后不超过s的球员结尾的球队能获得的最大分数和。这听起来有点绕接下来我们会用代码厘清。4. 离散化结合动态规划的最终方案4.1 算法思路再梳理与状态设计让我们摒弃最初的二维DP幻想拥抱离散化后的一维DP。整个算法流程如下绑定与排序将每个球员的年龄和分数绑定为一个对子(age, score)。然后对所有球员进行排序第一关键字为年龄升序第二关键字为分数升序。这样我们保证了在遍历时年龄是非递减的且同龄人中分数小的在前。分数离散化提取所有球员的分数进行排序和去重得到离散化数组sorted_scores。DP状态定义定义dp[i]其中i是分数在sorted_scores中的索引。dp[i]的含义是在已经遍历过的球员中年龄均不超过当前考虑的年龄能够组成一个“无矛盾”球队且球队中最后一名球员的分数离散化后恰好等于sorted_scores[i]时球队的最大总分数。注意这个定义是“以特定分数结尾”而不是“分数不超过i”。后者通常用于求LIS长度但这里我们要求最大和且需要知道结尾的具体分数来进行转移。DP转移方程我们按排序后的顺序遍历每个球员(age, score)。首先找到当前球员分数score在sorted_scores中的离散化索引idx。现在我们需要计算以当前球员作为球队最后一人时的最大分数和current_max。要组成这样的球队之前的球队最后一名球员的分数不能超过score即分数索引不能大于idx。所以我们需要在dp[0]到dp[idx]中找到一个最大值max_prefix。那么current_max max_prefix score。同时当前球员也可以独自成队所以current_max至少应为score。然后我们用current_max去更新dp[idx]。注意这里不是简单的赋值而是dp[idx] max(dp[idx], current_max)。因为可能有其他同样以分数sorted_scores[idx]结尾的球队总分数更高。然而这里有一个至关重要的点dp数组的定义是“在已遍历的球员中...”。当我们更新dp[idx]后这个更大的值可能会影响后续分数索引j idx的球员吗会的。因为对于后续一个分数更高的球员他在寻找max_prefix时会查看所有dp[0..j]。如果dp[idx]变大了那么后续球员计算max_prefix时就有可能受益。因此我们不能在遍历所有球员的循环内部让本次更新的dp[idx]立即被同一次循环中更后面的球员使用。这会导致状态依赖关系混乱相当于考虑了同年龄或更小年龄但排序在后的球员这与事实不符。正确的做法是在每处理完一个年龄组或者更精确地说在每处理完一个球员后但为了处理同龄人需要缓冲后再统一更新dp数组。或者更简单且安全的方法是我们使用一个临时数组new_dp来存储本次遍历中所有球员计算出的current_max在处理完所有年龄相同的球员后再用new_dp中的值去更新全局的dp数组。这是因为年龄相同的球员之间没有顺序限制他们可以任意组合我们必须等所有同龄人的新状态都计算出来后再一起更新才能保证他们之间能互相看到彼此更新前的状态即避免互相干扰。对于年龄严格递增的情况则可以直接更新。4.2 C代码实现与逐行解析理解了上述思路我们来看代码实现。这里采用一种更清晰、无需按年龄组缓冲的实现方式在遍历排序后的球员时对于每个球员我们基于当前时刻的dp数组它代表了所有年龄严格小于当前球员的球员所构成的状态来计算其current_max然后将其存储起来最后再更新。但由于年龄可能相等我们需要确保所有年龄相等的球员都基于同一个“历史”dp状态来计算。#include vector #include algorithm using namespace std; class Solution { public: int bestTeamScore(vectorint scores, vectorint ages) { int n scores.size(); vectorpairint, int players; // (age, score) for (int i 0; i n; i) { players.emplace_back(ages[i], scores[i]); } // 关键排序年龄升序同龄则分数升序 sort(players.begin(), players.end()); // 1. 分数离散化 vectorint all_scores scores; sort(all_scores.begin(), all_scores.end()); all_scores.erase(unique(all_scores.begin(), all_scores.end()), all_scores.end()); int m all_scores.size(); // 2. 初始化DP数组。dp[i] 表示以离散化分数i结尾的球队最大总分。 vectorint dp(m, 0); int ans 0; // 3. 遍历球员 // 由于已排序年龄是非递减的。我们需要处理年龄相同的情况。 // 方法遍历每个球员但更新延迟。 vectorint updates(m, 0); // 临时存储本次年龄组内计算出的新dp值 int i 0; while (i n) { int current_age players[i].first; // 清空临时更新数组准备收集本次年龄组的所有可能更新 fill(updates.begin(), updates.end(), 0); // 处理所有年龄为 current_age 的球员 int j i; while (j n players[j].first current_age) { int score players[j].second; // 找到当前分数的离散化索引 int idx lower_bound(all_scores.begin(), all_scores.end(), score) - all_scores.begin(); // 计算以该球员结尾的最大分数和 // 需要查询 dp[0...idx] 的最大值 int max_prefix 0; // 这里可以用循环但为了优化我们可以维护一个前缀最大值数组。 // 简单起见先使用循环后续可以优化。 for (int k 0; k idx; k) { max_prefix max(max_prefix, dp[k]); } int current_max max_prefix score; // 球员也可以单独成队 current_max max(current_max, score); // 记录更新我们需要保留所有以idx结尾的可能性中的最大值 updates[idx] max(updates[idx], current_max); ans max(ans, current_max); // 更新全局答案 j; } // 所有同龄球员处理完毕现在将updates合并到dp中 for (int k 0; k m; k) { dp[k] max(dp[k], updates[k]); } i j; // 移动到下一个年龄组 } return ans; } };代码解析与优化点排序sort(players.begin(), players.end())利用了pair的默认比较规则先比较first再比较second完美实现了“年龄升序同龄分数升序”。离散化all_scores存储了所有不同的分数并排序。lower_bound用于快速将原始分数映射到索引。DP核心循环最外层的while (i n)用于按年龄组处理。内层while (j n players[j].first current_age)处理所有同龄球员。状态转移对于每个球员计算max_prefix需要查询dp[0..idx]的最大值。上面的代码用了O(m)的循环这使得总时间复杂度为 O(n * m)在最坏情况下n1000 m1000约为1e6加上外层年龄组循环常数较大但仍在可接受范围约1e9次操作这里需要仔细算最坏情况每个球员年龄都不同则年龄组数为n每个球员内层循环查询前缀最大值为O(m)总复杂度O(n² * m)不对这样太高了。这里存在误解。实际上在年龄都不同的最坏情况下外层循环n次内层每个球员循环中查询前缀最大值如果暴力循环是O(m)次那么总复杂度是O(n * m)。由于m最大为n所以是O(n²)。对于n1000是1e6次操作完全可以接受。代码中的双重while循环并不会导致立方复杂度因为内层while对于每个年龄组只执行一次而每个球员只会被处理一次。延迟更新updates数组是关键。它确保了所有同龄球员在计算自己的current_max时看到的dp数组都是上一个年龄组结束后的状态从而避免了同龄球员之间的状态干扰。在所有同龄球员都计算完毕后再一次性用updates更新dp。4.3 终极优化树状数组Fenwick Tree或线段树上述代码中的for (int k 0; k idx; k)循环查询前缀最大值是O(m)的。我们可以用树状数组Binary Indexed Tree, BIT或线段树将其优化到 O(log m)。树状数组通常用于维护前缀和但经过巧妙设计它也可以维护前缀最大值前提是更新操作是“取最大值”而非“增加”。我们可以定义一个树状数组bit其中bit.query(idx)返回dp[0..idx]中的最大值。当我们需要更新dp[idx]时调用bit.update(idx, new_value)这个操作会在树状数组内部确保所有相关区间都更新了最大值。使用树状数组后每个球员的处理时间从 O(m) 降为 O(log m)总时间复杂度从 O(n * m) 降为 O(n log m)对于 n1000, m1000效率提升显著。下面是结合了树状数组的优化版本代码#include vector #include algorithm using namespace std; class FenwickTreeMax { private: vectorint tree; int n; public: FenwickTreeMax(int size) : n(size), tree(size 1, 0) {} // 将位置idx的值更新为val取最大值 void update(int idx, int val) { idx; // 树状数组通常从1开始索引 while (idx n) { tree[idx] max(tree[idx], val); idx idx -idx; } } // 查询前缀 [0, idx] 的最大值 int query(int idx) { idx; int res 0; while (idx 0) { res max(res, tree[idx]); idx - idx -idx; } return res; } }; class Solution { public: int bestTeamScore(vectorint scores, vectorint ages) { int n scores.size(); vectorpairint, int players; for (int i 0; i n; i) { players.emplace_back(ages[i], scores[i]); } sort(players.begin(), players.end()); // 离散化分数 vectorint all_scores scores; sort(all_scores.begin(), all_scores.end()); all_scores.erase(unique(all_scores.begin(), all_scores.end()), all_scores.end()); int m all_scores.size(); FenwickTreeMax bit(m); int ans 0; // 由于已排序我们可以顺序处理但为了处理同龄人仍需缓冲或按组更新。 // 更优雅的方式顺序遍历但用临时变量存储当前年龄组的更新最后统一apply到BIT。 // 但BIT不支持批量“取最大值”更新。我们可以换种思路 // 对于每个球员直接基于当前BIT查询结果计算然后立即更新BIT。 // 这会有问题吗考虑两个同龄球员A(分5), B(分3)。按分数升序排后先处理B。 // B查询前缀max(对应分数3)更新BIT[3]。 // 然后处理A查询前缀max(对应分数5)此时BIT[3]已被B更新所以A能看到B的结果。 // 但这是允许的因为A和B年龄相同他们可以同时在球队中且A分数高B分数低满足非递减条件。 // 所以对于年龄相同且按分数升序排序的情况直接顺序处理并立即更新BIT是安全的。 // 因为后处理的球员分数高可以看到先处理的球员分数低更新后的状态这正好符合“同龄人可同队”的规则。 // 对于年龄更大的球员他们看到的是所有之前年龄包括同龄球员更新后的最终状态也是正确的。 for (int i 0; i n; i) { int score players[i].second; int idx lower_bound(all_scores.begin(), all_scores.end(), score) - all_scores.begin(); // 查询当前BIT中分数索引不超过idx的最大球队总分 int current_max bit.query(idx); // 加上当前球员的分数或者从当前球员重新开始 current_max max(score, current_max score); // 用 current_max 更新 BIT 中 idx 位置的值取最大值 bit.update(idx, current_max); ans max(ans, current_max); } return ans; } };这个版本是最终推荐版本它简洁且高效。其正确性基于排序和离散化球员按(年龄分数)升序排序。遍历时对于球员iBIT中存储的是所有年龄小于等于当前球员年龄且分数索引不超过某个值的最大球队总分。但由于BIT的更新是即时生效的对于同龄且分数更小的球员他们会被先处理并更新BIT因此当前球员在查询时能看到他们。这恰好符合“同龄球员只要分数非递减即可同队”的规则。bit.query(idx)获取的是以分数不超过all_scores[idx]的球员结尾的球队最大总分。然后我们尝试将当前球员接在这样的球队后面或者自己单独成队。bit.update(idx, current_max)确保了BIT中记录的是以分数索引idx结尾的球队最大总分。由于BIT维护的是前缀最大值这个更新会影响到所有包含idx的区间。时间复杂度排序 O(n log n)离散化 O(n log n)主循环中每次查询和更新BIT为 O(log n)总复杂度 O(n log n)。空间复杂度 O(n)。5. 总结与扩展思考通过LeetCode 1626这道题我们深入实践了动态规划与离散化这一组合技。面对定义域巨大的多维DP问题离散化通过压缩有效坐标将不可能变为可能。而树状数组的引入则进一步将区间查询优化到对数级别展现了算法优化的层次感。回顾几个关键点排序预处理将双变量约束转化为单变量分数的非递减子序列问题是简化问题的第一步。排序规则年龄升序、同龄分数升序至关重要它确保了状态转移的正确性。离散化的本质关注相对顺序而非绝对数值。在C中sort、unique、lower_bound是三件套。状态设计从最直观的二维DP到离散化后的一维DP配合排序再到使用树状数组维护前缀最大值。每一步优化都建立在对问题更深的理解上。树状数组的妙用它不仅用于求和通过定义合适的合并操作max它可以高效维护前缀最大值非常适合此类DP优化。扩展思考如果“无矛盾”条件变成年龄和分数都严格递增该如何修改只需要将排序规则中第二关键字改为分数升序保持不变但在状态转移时查询bit.query(idx-1)而不是bit.query(idx)因为严格递增要求之前的分数必须小于当前分数。如果每个球员还有一个“权重”目标是最大化权重和而非分数和算法需要如何调整只需要将代码中的score替换为weight并在计算current_max时加上weight即可。DP的核心结构不变。这道题很好地体现了算法竞赛和面试中常见的思维模式从暴力解出发识别瓶颈维度爆炸应用标准技巧离散化进行压缩再使用高级数据结构树状数组/线段树进行优化。掌握这个套路你就能应对一大批类似的“带权值LIS”或“二维偏序”问题。

动态规划与离散化：解决LeetCode 1626双约束优化问题

相关推荐

API额度周期管理实战：从监控预警到智能优化策略

如何5分钟搞定音乐歌词获取？163MusicLyrics免费歌词下载神器完整指南

MaixCAM IMU零飘抑制：基于动态零偏估计与互补滤波的姿态解算实践

更多资讯

Docs-as-Code 实践指南：用 agency-agents-zh 的技术文档工程师智能体，把复杂工程写成开发者爱读的文档

Android系统定制：包名白名单放开DEVICE_POWER权限实现应用主动灭屏

VBA一键汇总多个Excel工作簿同名工作表指定区域数据

基于Python的药店药品管理系统源码解析与毕业设计实战指南

KingbaseES集群节点平滑退出为单实例的实践与避坑指南

如何实时掌握用户健康数据：Open Wearables Webhooks 完整配置与调试教程

今日更新

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？