1. 项目概述从“对局匹配”到动态规划实战看到“蓝桥杯国赛 对局匹配DP”这个标题很多参加过算法竞赛的朋友可能会心一笑或者眉头一皱。这确实是一道经典的、有一定区分度的动态规划题目。它不像简单的斐波那契数列那样直白也不像复杂的树形DP那样需要庞大的前置知识它恰好卡在一个“需要你真正理解DP思想并能灵活建模”的难度上。这道题的核心是要求我们在一个给定的选手分数列表中挑选出尽可能多的选手进行匹配对局但有一个关键限制任意两个被选中的选手他们的分数差不能等于一个给定的整数k。目标是最大化选中选手的数量。初看之下你可能会想“这不就是贪心或者排序后直接选吗”但稍微深入思考就会发现陷阱。比如当k2分数为[1, 3, 3, 5]时如果你贪心地从最低分开始选选了1就不能选3因为1和3差2然后选另一个3再选55和3差2冲突最终选了[1, 3, 5]共3人。但最优解其实是选两个3共2人吗不对这里最优解是[1, 3]或者[3, 5]也是2人等等让我们仔细算算。实际上如果选[1, 3]分数为1和3的选手可以匹配吗题目是“对局匹配”选中的人是要两两匹配的但限制是任意两人分数差不能等于k。如果只选两个人他们俩自然就是一对只要他俩分数差不为k即可。所以[1, 3]差2等于k冲突不能同时选。[3, 5]同理冲突。两个3分数相同差0可以同时选。所以最优解就是选两个3共2人。看这里贪心选1反而导致了次优解选了1就逼得你不能选任何一个3最终可能只能选1和5但1和5差4不冲突所以[1, 5]也是2人。但[1, 5]和[3, 3]都是2人似乎贪心也没错我们再看一个例子分数[1, 1, 3, 3, 5]k2。最优解是选[1, 1, 5]或[3, 3, 5]共3人。如果从低分贪心选1那么下一个3不能选冲突再下一个3不能选然后可以选5得到[1, 1, 5]这恰好是最优解之一。但如果分数是[1, 3, 3, 3, 5]呢最优解是选[3, 3, 3]共3人。贪心从1开始选了1就不能选3最终可能只能选[1, 5]共2人就错了。所以这个问题无法用简单的贪心解决因为当前的选择会影响到后续一系列的选择。这种“当前状态影响未来决策”的特性正是动态规划DP大显身手的场景。这道题的精妙之处在于它将一个看似是“匹配”的问题通过巧妙的转化变成了一个在多个相互独立的子序列上的分组背包问题或者更具体地说是多个打家劫舍问题的叠加。接下来我将彻底拆解这道题的解题思路、DP状态设计、转移方程推导以及代码实现中的每一个细节并分享我在调试这类问题时的实战心得。2. 核心思路拆解化整为零与状态设计面对一个复杂问题DP的第一步永远是定义状态。对于“对局匹配”最直接的想法可能是定义dp[i]为考虑前i个选手按分数排序后时能选出的最大人数。但这样定义会遇到麻烦第i个选手选或不选不仅仅取决于前一个选手i-1还可能取决于前面某个分数恰好与它相差k的选手。这个依赖关系不是相邻的而是跳跃的使得状态转移非常困难。这里就需要一个关键的洞察分数差为k的选手之间会互相制约而分数差不为k倍数的选手之间是互不影响的。更准确地说如果我们把所有选手的分数对k取模那么分数模k同余的选手他们之间的分数差一定是k的整数倍。例如所有分数为1, 1k, 12k, 13k...的选手他们模k都余1。关键点来了对于模k余数不同的两组选手他们之间的分数差绝对不可能等于k。因为如果两个数a和b满足|a-b|k那么a和b模k的余数一定是相同的你可以自己验证一下如果a % k r那么(a±k) % k r。这个性质至关重要它意味着整个问题可以被分解为k个完全独立的子问题。每个子问题对应一个余数r(0 r k)我们只需要处理所有分数模k等于r的选手。因为不同余数之间的选手绝对不会因为“分数差为k”这个限制而产生冲突所以我们可以分别求出每个余数分组下能选出的最大人数最后把k个分组的结果简单相加就是全局最优解。那么对于一个特定的余数分组问题简化成了什么假设k3我们看余数为1的分数可能是1, 4, 7, 10, 13...。这些分数在数轴上是一串等差数列。题目限制是“选中的人里任意两人分数差不能等于k即3”。在我们这个分组里分数差为3意味着两个分数在数列中是相邻的项。例如1和4差34和7差3但1和7差6不被禁止。所以在单个余数分组内问题进一步转化为了给定一个有序列表分数从中选取尽可能多的数但不能同时选取相邻的两个数因为相邻分数差为k。有没有觉得很眼熟这就是经典的“打家劫舍”问题LeetCode 198的变种在“打家劫舍”中你不能偷窃相邻的房屋在这里你不能选取相邻分数在按大小排序后的本分组序列中的选手。但是还有一个细微差别。在标准的打家劫舍中每个房屋有一个价值金额我们要最大化总金额。在我们这里每个“分数”可能对应多个选手分数相同。假设分数s出现了cnt[s]次。那么如果我们决定在最终方案中“选取”这个分数我们其实可以把这个分数的所有cnt[s]个选手都选上因为他们分数相同差为0不违反规则。而“不选取”这个分数就意味着这个分数的所有选手都不选。于是对于单个余数分组我们将其所有分数按大小排序得到一个序列[s1, s2, s3, ..., sm]每个分数si有一个“价值”vi cnt[si]即该分数的人数。问题变为从这个序列中选取一个子集使得被选取的分数在序列中不相邻并且最大化被选取分数的价值总和。我们可以为此设计DP状态。令dp[i]表示考虑前i个分数时能获得的最大总人数价值。状态转移方程不选第i个分数那么最大人数就是前i-1个分数的结果即dp[i-1]。选第i个分数那么第i-1个分数绝对不能选因为相邻。因此最大人数是前i-2个分数的结果加上第i个分数的人数即dp[i-2] cnt[si]。两者取最大值dp[i] max(dp[i-1], dp[i-2] cnt[si])。这就是单个分组内的核心DP。边界条件dp[0] 0没有分数dp[1] cnt[s1]只有一个分数全选。这里有一个非常重要的注意事项当k0时怎么办此时“分数差不能等于k”意味着“分数差不能等于0”即不能选择任何两个分数相同的选手。所有选手只要分数相同就互相冲突。因此对于k0的情况问题退化为在给定的分数列表中每个分数最多只能选一个人。那么答案就是不同分数的个数。这是一个特例需要在代码开始时单独处理。3. 算法实现与细节剖析思路清晰之后我们来看如何用代码实现。整个过程可以分为四个步骤数据统计、分组处理、分组内DP、结果汇总。3.1 数据预处理与统计首先我们需要统计每个分数出现了多少次。通常输入是一个数组scores。我们可以使用一个数组cnt或者哈希表如Python的defaultdict(int)C的map来记录。cnt[x]表示分数x出现的次数。这里有一个性能考量。分数的范围可能很大题目一般会给出上限比如10^5。使用数组需要提前声明大小如果分数范围未知或很大但稀疏用哈希表更省内存。在竞赛中通常题目会明确分数范围使用数组访问更快。# 假设 scores 是分数列表n 为人数 n len(scores) max_score max(scores) # 或者根据题目范围确定 cnt [0] * (max_score 1) # 确保索引范围覆盖 for s in scores: cnt[s] 13.2 处理 k0 的特殊情况如前所述k0时规则变为不能选择分数相同的选手。那么最优策略就是每种分数只选一个人。所以答案就是有多少个不同的分数即cnt数组中值大于0的元素个数。if k 0: # 统计有多少个分数出现过 ans sum(1 for c in cnt if c 0) print(ans) return3.3 分组动态规划这是算法的核心。我们需要对余数r从0到k-1进行循环。对于每个余数r我们收集所有分数s满足s % k r。注意这些分数在数轴上并不一定是连续的比如分数1, 4, 7, 100都满足模3余1但1,4,7是连续的等差数列100则离得很远。这有关系吗有因为我们的DP定义在“按大小排序后的分数序列”上并且“相邻”指的是在这个序列中位置相邻而不是数值上差k。数值差k只是我们分组和定义“相邻冲突”的依据。一旦我们按数值大小取出某个余数分组的所有分数它们自然就是递增的并且相邻项之差是k的倍数。我们的规则禁止的是选取序列中相邻的两个分数这正是因为相邻分数之差恰好为k或者更准确地说至少为k且是k的最小倍数因为中间没有其他同余数的分数。因此对于每个余数分组我们得到的是一个递增的分数列表[s1, s2, s3, ...]其中s(i1) - s(i)是 k 的正整数倍。通常为了DP方便我们不需要显式存储分数值只需要按顺序遍历该余数对应的所有分数即可。我们可以通过一个循环从r开始每次步进k直到超过最大分数来遍历所有可能的分数。ans 0 for r in range(k): # 遍历每个余数分组 # 提取该分组下所有存在的分数按升序 # 我们可以直接遍历分数值也可以先收集到一个列表里。 # 方法一直接DP不显式存储列表更高效 # 我们需要知道前一个分数和前前一个分数的DP值。 # 由于分数可能不连续如1, 4, 7, 100我们需要处理“跳跃”。 # 更稳健的方法是方法二先收集分数和对应人数。 group_scores [] s r while s max_score: if cnt[s] 0: # 这里存储的是 (分数值, 人数) 或者只存储人数 # 对于DP我们只关心人数cnt[s]分数值仅用于确定顺序而顺序已经由遍历顺序sk保证。 group_scores.append(cnt[s]) s k m len(group_scores) if m 0: continue # 这个分组没人跳过 # 开始对这个分组进行DP # dp0, dp1 分别表示 dp[i-2], dp[i-1] dp0 0 # 对应 dp[i-2]初始时 i1 dp[-1]视为0 dp1 group_scores[0] # 对应 dp[0]第一个元素必选因为只有一个时选它最优 # 注意这里dp1初始化为group_scores[0]对应的是只有一个分数时的最优解。 # 但我们的DP递推是从第二个元素索引1开始的。 for i in range(1, m): # 当前考虑 group_scores[i] # 选择当前分数dp0 group_scores[i] # 不选当前分数dp1 current max(dp1, dp0 group_scores[i]) # 滚动更新 dp0, dp1 dp1, current # 循环结束后dp1 存储的就是这个分组的最优解 ans dp1关键细节与纠错 上面的代码有一个常见的初始化错误。让我们仔细分析一下标准“打家劫舍”的DP。对于序列values(即这里的group_scores)。定义dp[i]为考虑前i1个元素即values[0...i]时的最大和。dp[0] values[0]dp[1] max(values[0], values[1])对于i 2:dp[i] max(dp[i-1], dp[i-2] values[i])而在我们上面的滚动数组实现中dp0初始应代表i0之前的状态即没有元素值为0。dp1初始应代表i0时的状态即dp[0] values[0]。然后我们开始循环i从1到m-1。对于i1计算current max(dp1, dp0 values[1])。这正好对应dp[1] max(dp[0], dp[-1]values[1])其中dp[-1]视为0。所以dp[1] max(values[0], values[1])。正确。然后更新dp0, dp1 dp1, current。所以上面的代码初始化dp1 group_scores[0]是正确的。循环从i1开始也是正确的。但是这里有一个边界情况如果m 1我们根本不会进入循环直接ans dp1而dp1就是group_scores[0]正确。如果m 0我们已经跳过。所以代码逻辑是完备的。3.4 复杂度分析与优化时间复杂度我们遍历了所有可能的分数。外层循环k次内层循环遍历所有分数。每个分数最多被访问一次当它属于某个余数分组时。因此总时间复杂度是O(N M)其中N是选手人数M是分数最大值或范围。如果使用哈希表统计且按余数分组时也通过哈希表查找复杂度可视为O(N)。空间复杂度主要消耗在cnt数组O(M)和分组列表O(N)最坏但通常更小。使用滚动数组进行DP空间为O(1)。一个重要的优化点我们真的需要显式构造group_scores列表吗对于每个余数分组分数是每隔k递增的。我们可以直接在循环变量s上应用滚动DP这样空间复杂度更低。ans 0 for r in range(k): # 使用 prev2 和 prev1 作为滚动数组 prev2 0 # dp[i-2] prev1 0 # dp[i-1]注意初始化与之前不同 s r # 我们需要按顺序处理分数。prev1需要能在遇到第一个有效分数时被正确设置。 # 一种方法是记录上一个有效的分数值。 last_score -1 # 上一个处理过的分数值 while s max_score: if cnt[s] 0: # 计算当前分数与上一个分数的“距离” if last_score -1: # 这是第一个有效分数 current cnt[s] else: # 检查当前分数s和last_score是否“相邻” # 在同一个余数分组里分数是等差数列差为k的倍数。 # “相邻”意味着 (s - last_score) k if s - last_score k: # 相邻不能同时选 # 此时prev1是考虑last_score为止的最优解 # prev2是考虑last_score的上一个分数为止的最优解 # 对于当前分数s选它 - prev2 cnt[s]不选它 - prev1 current max(prev1, prev2 cnt[s]) else: # 不相邻比如 last_score1, s7 (k3)中间跳过了4。 # 这意味着分数4不存在cnt[4]0。那么last_score1和s7之间没有冲突。 # 因此s可以无脑选最优解就是 prev1 cnt[s] current prev1 cnt[s] # 滚动更新 prev2, prev1 prev1, current last_score s s k # 这个分组处理完后prev1就是该分组的最优解 ans prev1这种实现更高效但逻辑稍微复杂一些需要处理分数不连续中间某些分数缺失的情况。当分数不连续时当前分数与上一个有效分数不相邻因此没有冲突可以直接累加。这其实是更通用的解法。第一种方法显式构造列表隐含了“缺失的分数对应人数为0”在列表中表现为一个0值。在DP方程max(dp[i-1], dp[i-2] values[i])中如果values[i]为0那么dp[i] max(dp[i-1], dp[i-2])这会导致状态“跳过”这个缺失的位置效果与第二种方法中判断“不相邻则直接累加”是等价的。显式构造包含0的列表更容易理解和编码。4. 完整代码实现与测试结合以上所有步骤这里给出一个清晰、完整的Python实现包含详细的注释。def max_matching_players(scores, k): 计算在“对局匹配”规则下能选出的最大玩家数。 :param scores: List[int], 所有玩家的分数列表 :param k: int, 规定的分数差限制 :return: int, 最大可选玩家数 if not scores: return 0 # 1. 统计每个分数的人数 max_score max(scores) cnt [0] * (max_score 1) for s in scores: cnt[s] 1 # 2. 处理 k0 的特殊情况 if k 0: # 每种分数最多选一人 return sum(1 for c in cnt if c 0) total_players 0 # 3. 对每个余数分组进行DP for r in range(k): # 收集该分组下所有分数按升序这里存储的是人数 group [] s r while s max_score: if cnt[s] 0: group.append(cnt[s]) s k m len(group) if m 0: continue # 使用滚动数组进行打家劫舍DP # dp0 表示 dp[i-2], dp1 表示 dp[i-1] dp0 0 dp1 group[0] # 初始化只有第一个元素时 for i in range(1, m): # 当前状态选 i 则 dp0 group[i]不选则 dp1 current max(dp1, dp0 group[i]) dp0, dp1 dp1, current # dp1 即为本分组最优解 total_players dp1 return total_players # 测试用例 if __name__ __main__: # 示例1: 题目可能给的简单例子 scores1 [1, 3, 3, 5] k1 2 print(fscores{scores1}, k{k1}, max players{max_matching_players(scores1, k1)}) # 预期输出 2 # 示例2: 更复杂的例子 scores2 [1, 1, 3, 3, 3, 5, 5, 7] k2 2 # 分组余0: [] - 0 # 分组余1: [1,1], [3,3,3], [5,5], [7] - 序列人数 [2, 3, 2, 1] # DP: [2] - 2; [2,3] - max(2,03)3; [2,3,2] - max(3,22)4; [2,3,2,1] - max(4,31)4 # 分组余0: 无 # 总和 4 print(fscores{scores2}, k{k2}, max players{max_matching_players(scores2, k2)}) # 预期输出 4 # 示例3: k0 scores3 [1, 2, 2, 3, 3, 3] k3 0 print(fscores{scores3}, k{k3}, max players{max_matching_players(scores3, k3)}) # 预期输出 3 (分数1,2,3) # 示例4: 大范围分数测试性能 import random scores4 [random.randint(0, 10000) for _ in range(10000)] k4 17 # 只是测试运行不验证结果 result max_matching_players(scores4, k4) print(fLarge scale test done. Result: {result})5. 常见错误与调试心得这道题在实现时有几个坑点很容易让人栽跟头。错误1错误理解“匹配”含义题目叫“对局匹配”容易让人联想到需要两两配对。但仔细读题它只是说要“匹配”最终选出的选手数量就是答案。并没有要求选出的人必须恰好组成若干对即人数为偶数。所以这是一个简单的选取问题而不是复杂的配对问题。这是最重要的第一步理解如果理解成必须配对就会去想复杂的图匹配算法完全走偏。错误2未考虑分数重复人数这是最核心的建模难点。如果只是判断分数是否被选取那么每个分数只有选或不选两种状态价值为1。但事实上同一个分数可以有多个选手选取该分数意味着可以收获该分数的所有选手。因此DP中的“价值”应该是cnt[score]而不是1。很多人在自己推导时容易忽略这一点导致模型错误。错误3k0 未特殊处理当k0时“分数差不能等于0”意味着同分数的人不能同时被选。此时每个分数最多贡献1个人。如果你套用通用DP逻辑会发现余数分组只有一组余数0然后你对所有分数因为模0都余0做“打家劫舍”但这时“相邻”的定义失效了因为任何两个不同分数差都不为0但同分数差为0。通用算法会错误地将所有人数相加。所以必须单独处理。错误4DP状态转移初始化错误在实现滚动数组时dp0和dp1的初始化必须小心。对于每个分组如果分组只有一个有效分数那么最优解就是该分数的人数。如果分组有两个有效分数最优解是max(第一个分数人数, 第二个分数人数)。 我们的滚动初始化dp00, dp1group[0]然后从i1开始循环可以正确处理这两种情况。如果分组为空则跳过。错误5分组时未正确处理分数不连续在按余数r遍历分数s r; s max_score; s k时如果某个s的cnt[s]为0代表这个分数没有选手。在显式构造分组列表时我们通常只加入cnt[s] 0的分数。这样构造的列表是紧凑的列表中的相邻项在原始分数序列上可能并不相邻中间跳过了某些不存在的分数。例如分数[1, 7]模3都余1中间跳过了4。在我们的DP模型中1和7在分组列表中是相邻的但它们的分数差是6不等于k3。因此它们之间没有冲突应该可以同时选。但在我们的“打家劫舍”DP中默认列表相邻项冲突这就错了。修正方法 我们需要在分组列表中为那些不存在的分数保留位置值为0或者修改DP逻辑。保留0值是最简单的方法这样列表就变成了[cnt[1], cnt[4], cnt[7]]即[人数1, 0, 人数7]。此时DPdp[0] 人数1dp[1] max(dp[0], 0) 人数1因为cnt[4]0选不选都一样dp[2] max(dp[1], dp[0] 人数7) max(人数1, 人数1人数7)- 正确选择了1和7。 所以在构造分组列表时必须包含所有s, sk, s2k, ...的位置即使cnt[s]0也要放入0。这保证了列表索引的连续性相邻索引对应的分数差就是k。然而这样可能会让列表很长如果分数范围大而k小。更高效的方法是用第二种优化实现在遍历过程中动态判断当前分数与上一个有效分数是否真的相差k。调试技巧从小数据开始用手算几个简单例子比如[1,3,3,5], k2[1,1,3,3,5], k2[1,2,3,4,5], k1。在纸上画出分组模拟DP过程与程序输出对比。打印中间状态在代码中打印每个余数分组构造的列表group以及DP过程中的dp0,dp1,current值可以清晰看到计算过程。重点测试边界k0k1k大于最大分数所有分数都相同分数范围很大但数据稀疏等情况。理解本质始终记住这道题经过转化后就是多个独立的“打家劫舍”问题。如果你对“打家劫舍”非常熟悉这道题就成功了一大半。6. 总结与举一反三“对局匹配”这道题是一个非常好的动态规划教学案例它展示了如何通过问题转化将一个看似复杂的问题分解为若干个熟悉的经典模型。其核心步骤是识别约束约束“分数差不能为k”具有模k的同余性质。分解问题利用同余性质将原问题分解为k个互不干扰的子问题。模型转化在每个子问题同余分组内由于分数是等差数列约束“分数差不能为k”转化为“不能同时选取排序后相邻的元素”。同时每个元素具有权重人数。套用经典DP每个子问题变成了带权重的“打家劫舍”问题用标准的DP即可解决。合并结果将各子问题的解相加即得全局最优解。这种“分组独立DP”的思想非常常见。例如另一类经典问题“删除一些数字使得剩下的数字最大/最小且相邻数字差不大于k”有时也可以通过按余数分组后组内进行贪心或DP来解决。再比如一些资源分配问题如果资源之间有特定的冲突关系比如时间差、距离差也常常可以转化为图论中的独立集问题而在特定结构如链、环上独立集问题又可以用DP高效求解。在竞赛中遇到此类问题首先要冷静分析约束条件的内在数学结构寻找能否将元素分类使得类间无冲突从而化整为零。动态规划的魅力就在于它不仅能解决“最优子结构”问题更能通过巧妙的状态设计处理各种复杂的约束条件。这道“对局匹配”题无疑是一次精彩的DP思维训练。