区间DP解“拿糖果”：从贪心误区到最优策略实战解析

说实话我第一次看到“拿糖果”这道题的时候差点把它当成热身题给秒了。题面本身非常朴素有 n 堆糖果排成一行每堆糖果数量用一个整数数组表示两个人轮流从最左端或最右端拿走一整堆直到全部取完两个人都足够聪明目标是让自己最终拿到的糖果总数尽可能多问先手最多能拿多少。我当时第一反应是这有什么难的每次比较左右两端谁大取谁不就完了然后就被一组又一组测试数据教育了。后来我才意识到这道题几乎是为区间 DP 量身定做的经典模板它真正考的不是怎么贪心而是怎么从“整个区间的最终收益”去想问题而不是只盯着眼前的一步。这篇文章我要把这个题从题面拆到状态定义再从代码拆到调试完整过一遍适合刚学会背包、正准备往区间 DP 和博弈型题目过渡的读者参考。1. “拿糖果”到底在考什么一道伪装成贪心的区间DP题1.1 先还原题面不过是一排糖果、两个玩家和你来我往为了避免不同题库的输入格式差异我先把约定写清楚后面所有推导和代码都基于这个约定糖果排成一排每堆的数量记录在数组a[0..n-1]中a[i]表示第 i 堆的糖果个数。两个玩家交替行动。每轮只能取走当前这一排最左边或最右边的那一堆取走之后这堆糖果就从序列里消失。游戏一直进行到所有糖果都被取完最终谁手里的糖果总数更多谁就获胜或者题目只要求输出先手最多能拿到的总数。双方都采取最优策略也就是任何一个玩家在做出选择时都会考虑对手接下来可能做出的最优反应。如果题目里面约定糖果个数可以是 0那么边界情况会稍微多一点但核心的模型完全一样无非是多考虑“取走一堆 0 个糖果”是否合理。我后面会用正整数作为默认情况来讲解最后再补充边界测试的处理。这类题目还有一个很容易踩的坑有些题库里“拿糖果”指的是另一个完全不同的模型比如“有一大堆糖果每次只能拿 1 到 k 颗谁拿最后一颗谁赢”那属于巴什博弈。我下面说的全部是“从一排糖果的两端取一整堆”这个版本也是竞赛里更常出现的区间 DP 版“拿糖果”。做题前一定要先看清题面别拿着一个模板去套所有同名题。1.2 从“每次都取大端”说起一个反例就够贪心直觉为什么诱人因为每一步都拿“当前能拿的最大值”短期来看无论如何都不吃亏。但博弈题的麻烦恰恰在于你这一步多拿了可能把更大的机会暴露给对手。我当初就是被下面这个反例治好的数组只有 4 个数糖果序列[10, 100, 3, 9]如果先手采用“哪端大取哪端”的策略第一轮比较左右两端10 比 9 大先手取走 10。接下来对手面对区间[100, 3, 9]立刻取走 100。先手只能再取 9对手最后拿 3。最终比分是先手 19对手 103先手惨败。如果先手第一轮故意取走右端的 9情况就完全不同了。对手面对的是区间[10, 100, 3]他会发现无论取左端的 10 还是右端的 3100 都还留在场上而下一轮先手就能拿走 100。最终比分是先手 109对手 13先手大胜。只看第一轮取 10 好像比取 9 多拿了 1但取 10 之后把区间[100, 3, 9]留给了对手这个区间对对手来说收益极高他会拿到 103。反过来取 9 之后留给对手的区间[10, 100, 3]是个“陷阱区”100 卡在中间对手怎么选都很难把它真正装进自己口袋最终反而是先手拿到了 100。这就是局部最优和全局最优的经典差异。在博弈里每一个选择的价值不取决于你自己当时拿到了什么而取决于这个选择会把对手推到什么样的局面里。1.3 藏在题面里的博弈结构零和与最优策略这个游戏有一个很好的性质糖果总数从头到尾是固定的我称为total。先手最后拿 S后手就必然拿total - S。所以先手想要赢本质上就是让自己的 S 尽可能大而不需要太关心一些花里胡哨的路径。“最优策略”这个词也需要解释清楚。它不是说每个玩家每步都做“局部最大”的决定而是说每个玩家都足够聪明能看清整个局面选择一条让自己最终收益最大的路线。这意味着当前玩家选左端还是右端时必须把“我拿完之后对手在某一个子区间里的最优收益”也算进去。正因为如此这个问题天然适合动态规划从整个区间开始每一次选择都会把问题缩小成一个更短的区间而且无论前面是怎么达到这个区间的只要区间状态相同后续的最优收益就相同。这不就是典型的重叠子问题吗2. 为什么必须用区间DP状态定义与转移方程的完整推导2.1 子问题天然嵌套拿完一堆剩下的还是同一个游戏假设现在轮到某位玩家面对连续区间[l, r]也就是当前还剩下第 l 堆到第 r 堆糖果。他只有两个选择取左端a[l]或者取右端a[r]。拿完之后发生什么如果取左端剩下的区间是[l1, r]如果取右端剩下的区间是[l, r-1]。关键点在于剩下的区间里仍然是两个玩家轮流从两端取糖果规则完全没变只不过轮到了另一位玩家先手。所以我可以定义这样一个状态dp[l][r] 当前玩家在这个区间中先手时能获得的最大糖果总数注意这里的“当前玩家”只是一个相对概念。不管这个玩家是原始意义上的先手还是后手只要他接下来第一个拿糖果面对区间[l, r]他能拿到的最优结果就是dp[l][r]。这个定义的好处是我不需要区分两个人分别是谁只需要区分“当前先手的一方”和“另一个玩家”。边界也很直接当l r时区间只剩一堆糖果当前玩家直接取走所以dp[l][l] a[l]。2.2 转移方程用区间和减掉对手收益绕开繁琐模拟现在推导转移。假设当前玩家面对区间[l, r]区间内糖果总和记为sum(l, r)。如果当前玩家取左端a[l]他先拿到a[l]。对手接下来在区间[l1, r]先手按照dp的定义对手最多能拿到dp[l1][r]。区间[l, r]的总糖果数是固定的sum(l, r)其中对手拿走的至多是dp[l1][r]那么剩下的糖果最终都会归当前玩家所有。所以当前玩家的总收益是a[l] (sum(l1, r) - dp[l1][r]) sum(l, r) - dp[l1][r]如果当前玩家取右端a[r]同理收益是sum(l, r) - dp[l][r-1]当前玩家会在这两个方案里选更大的那个因此dp[l][r] max( sum(l, r) - dp[l1][r], sum(l, r) - dp[l][r-1] )由于两项都包含相同的sum(l, r)进一步化简为dp[l][r] sum(l, r) - min(dp[l1][r], dp[l][r-1])这个形式非常清爽当前玩家的最优收益等于整个区间糖果总和减去留给对手的那个子区间里“对手能拿到的最小最优收益”。这里有个值得停下来想一想的点min(dp[l1][r], dp[l][r-1])并不是“对手会被迫选较差的那一个”而是当前玩家可以通过选择左端或右端来决定把哪个子区间留给对手。当前玩家当然会选择让对手后续收益更小的那个方案所以取的是min。整个推导绕过了逐轮模拟的复杂过程只用“区间总和减对手收益”就把两个人的博弈压缩进了一个公式这是区间 DP 在这类题上最漂亮的地方。2.3 手推一遍四元素样例亲眼看到DP如何“看见”最优解用前面那个反例[10, 100, 3, 9]完整推一遍你就能直观看到 DP 表是怎么填出来的。先初始化长度为 1 的区间dp[0][0] 10 dp[1][1] 100 dp[2][2] 3 dp[3][3] 9然后按区间长度从 2 开始逐步扩大。长度为 2区间总和计算结果[0,1]110110 - min(dp[1][1]100, dp[0][0]10) 100[1,2]103103 - min(dp[2][2]3, dp[1][1]100) 100[2,3]1212 - min(dp[3][3]9, dp[2][2]3) 9长度为 3区间总和计算结果[0,2]113113 - min(dp[1][2]100, dp[0][1]100) 13[1,3]112112 - min(dp[2][3]9, dp[1][2]100) 103长度为 4dp[0][3] 122 - min(dp[1][3]103, dp[0][2]13) 109所以先手最优能拿 109后手只能拿 13。和前面手动模拟的结果完全一致。注意dp[0][2] 13和dp[1][3] 103这两个值的巨大差距区间[10, 100, 3]对“当前先手”来说几乎是陷阱因为 100 卡在中间谁先手谁吃亏而区间[100, 3, 9]则对先手非常有利因为 100 就在左端先手可以直接拿走。所以先手第一轮取 9 而不是取 10本质上是在“把坏区间扔给对手把好区间留给自己”。这就是 DP 表背后隐含的战略判断。3. 两种代码实现与三个高频易错点3.1 记忆化搜索版直觉最先想到的正确写法如果先写自顶向下的递归思路最接近刚才的推导。用functools.lru_cache做记忆化配上前缀和数组快速求区间和代码可以非常短from functools import lru_cache def max_candy(a): n len(a) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] a[i] def range_sum(l, r): return pre[r 1] - pre[l] lru_cache(None) def dp(l, r): if l r: return a[l] return range_sum(l, r) - min(dp(l 1, r), dp(l, r - 1)) return dp(0, n - 1)这个版本有一个好处你完全不用关心区间长度的枚举顺序因为递归天然是先调用小子区间。只要边界条件写对dp(l, r)依赖的dp(l1, r)和dp(l, r-1)都会在更短区间上被计算出来。需要注意Python 默认递归深度差不多是 1000 层如果n大于 1000要么适当调高递归深度要么改用下面的自底向上版本。不过对于绝大多数区间 DP 题的规模n 在几百到几千之间记忆化搜索完全够用。3.2 自底向上递推版理解区间长度为什么必须放在外层自底向上版本的性能通常更好也更容易控制变量但循环顺序是最大的坑。正确写法是这样的def max_candy_dp(a): n len(a) pre [0] * (n 1) for i in range(n): pre[i 1] pre[i] a[i] dp [[0] * n for _ in range(n)] for i in range(n): dp[i][i] a[i] for length in range(2, n 1): for l in range(n - length 1): r l length - 1 total pre[r 1] - pre[l] dp[l][r] total - min(dp[l 1][r], dp[l][r - 1]) return dp[0][n - 1]为什么必须把length放在外层因为dp[l][r]依赖的两个状态dp[l1][r]和dp[l][r-1]它们的区间长度都是length - 1。如果先枚举左端点l再枚举右端点r比如写成for l in range(n): for r in range(l, n): ...那么计算dp[l][r]时dp[l1][r]里的l1比当前的l更大这一行可能还没开始处理取到的就是初始值 0答案自然全错。只有按区间长度从小到大枚举才能保证任何length状态所依赖的length-1状态都已经算好了。这个坑很隐蔽因为 n 很小的时候可能碰巧能过一两个样例但数据一复杂就大面积 WA。3.3 三个写代码时最容易翻车的细节第一个细节递归版忘记记忆化。如果直接写一个不带lru_cache的递归dp(l, r)时间复杂度会变成指数级n稍大就会超时。这是最简单的错误但也是最常见的。第二个细节前缀和的 0/1 下标混淆。我统一使用pre[i 1] pre[i] a[i]这样区间[l, r]的和就是pre[r 1] - pre[l]。如果写成pre[r] - pre[l]或者pre[r] - pre[l - 1]都会在下标边界上出问题尤其是l 0时很容易访问到pre[-1]。第三个细节dp[l][l] a[l]的初始化不能漏也不能错。长度 2 的区间依赖两个长度为 1 的边界状态如果边界是 0结果会整体偏小。另外如果题目允许 n 为 0那要单独返回 0但一般这种拿糖果的题 n 至少为 1所以我在代码里直接初始化长度为 1 的情况。还有个容易困惑的点dp[l][r]到底表示“总分”还是“净胜分”我前面一直用的是“当前玩家在区间内能拿到的最大糖果总数”。也有题解习惯用“当前玩家最终比对手多拿多少”来定义写成net[l][r] max(a[l] - net[l1][r], a[r] - net[l][r-1])两种定义都能做但千万别混用。如果你看到别人的代码里dp[l][r] max(a[l] - dp[l1][r], ...)那他用的就是净胜分的定义要用总分数值去对比需要保证定义一致。这一点在联调、对拍时特别重要。4. 复杂度、识别信号与同类题迁移4.1 复杂度评估O(n^2) 在所难免优化空间有限这个解法的时间复杂度是O(n^2)空间复杂度也是O(n^2)。状态数量总共是n * (n 1) / 2级别每个状态只做一次min和一次加减法转移是O(1)。所以 n 在 1000 到 2000 左右的规模跑起来非常轻松n 到 5000 时内存会开始吃紧二维数组大约是 n^2 个整数需要斟酌你是不是真的需要装下所有区间。能不能把空间压到一维其实可以因为dp[l][r]只依赖长度为length - 1的层滚动数组理论可行。但代价是代码可读性显著下降而且特别容易在“旧的上一层”和“正在写的当前层”之间绕晕。我的建议是除非内存限制真的很紧否则不压。区间 DP 题的核心价值在于把状态和转移推清楚而不是在空间优化上炫技。另外如果 n 大到上万那不是O(n^2)的问题这个模型本身就不合适了。那种题目往往有特殊性质比如糖果数组有规律或者只问胜负不问具体数量需要另找数学方法。见到 n 特别大的“拿糖果”先冷静判断是不是同名变体。4.2 什么时候该想到区间DP三条信号我在做题时判断一道题是不是区间 DP基本看三条信号操作对象是序列而且每次操作都发生在当前区间的某个端点。比如只能取最左或最右只能合并相邻两个只能删除两端的元素。操作之后问题会缩小成一个更短的连续区间而不是分裂成两个独立的子问题分裂成两个独立子问题的往往是四边形不等式或记忆化搜索但和经典区间 DP 略有差异。题目涉及“双方最优策略”或“若干步内最大/最小收益”而且状态只跟当前区间有关跟之前怎么走到这个区间无关。“拿糖果”这三条全占取左端或右端剩下的是连续区间双方轮流取未来收益只取决于剩余区间。所以一看到题面就该立刻往区间 DP 上想而不是在贪心上停留太久。4.3 与“拿石子”“预测赢家”的异同以及几个混淆变体“拿糖果”这个模型有一大票亲戚题。最常见的是“拿石子”两端版和“预测赢家”类题目它们的转移方程几乎一模一样都是dp[l][r] sum(l, r) - min(dp[l1][r], dp[l][r-1])但有些“拿糖果”变体完全不同我把容易混的几个列出来题型操作规则解法思路两端取一整堆本文每次取最左或最右的一堆区间 DP两端取任意连续若干堆每次从一端取走连续的一段直接区间 DP 不够需要转化单堆拿 1 到 k 颗只有一堆糖果每次可取 1 到 k 颗巴什博弈找模数周期多堆任取一堆每堆至少拿 1 颗每次从任意一堆取走至少一颗尼姆博弈异或判断胜负合并相邻糖果每次把相邻两堆合成一堆区间 DP但转移要枚举断点 k所以拿到题第一件事永远是看清楚规则是不是“只允许取两个端点中的一整堆”。只要这个前提成立下面这套sum - min的转移就是通解。5. WA排查与对拍调试的实战心得5.1 高频WA原因缓存、循环顺序、前缀和下标我见过不少人在这个题上反复 WA排在前三的原因基本就是递归没带记忆化导致超时而不是答案错。自底向上版本把l放外层、r放内层等价于没有按区间长度枚举导致一部分状态读到初始值 0。前缀和下标写错比如区间和写成了pre[r] - pre[l]在 l 恰好等于 0 时侥幸对换成其他区间就错。如果你 WA 了先按这个顺序自查先看你用的是总分定义还是净胜分定义再看递归有没有缓存再看循环顺序最后再看前缀和。不要在没确认这几个基础项前去怀疑算法本身。另外一个不太明显但也会卡人的问题是很多人拿到“双方都最优”的题会下意识以为要同时记录两个玩家的收益。其实在这个模型里完全没必要因为sum(l, r)是固定的当前玩家的收益确定之后另一个玩家的收益就是sum(l, r) - 当前玩家收益。记录一个值就够了。5.2 一个足够靠谱的调试套路无缓存递归对拍如果你对自己的递推实现没信心我推荐一个实测非常好用的调试方法写一个不带缓存、完全按照公式递归的“暴力版”作为参照然后随机生成小规模数组对拍两个版本的结果。无缓存递归版和dp公式完全同逻辑但它天然是自顶向下的不需要你手动控制区间长度顺序所以可以作为逻辑基准def solve_total(l, r): if l r: return a[l] total pre[r 1] - pre[l] return total - min(solve_total(l 1, r), solve_total(l, r - 1))然后写一个随机测试的小脚本import random for _ in range(1000): n random.randint(1, 8) a [random.randint(1, 20) for _ in range(n)] # 计算前缀和并调用两个函数断言结果一致n 小于等于 8 时递归深度很小即使没有记忆化也很快。如果对拍 1000 组都没问题那基本可以确定算法和实现是对的。之后再把 n 放大测性能。我还常用另一个对拍思路分别用“总分定义”和“净胜分定义”写两个版本然后断言总分版本结果 (total 净胜版本结果) / 2这样能同时验证两种定义下代码的一致性也能帮你排查是不是把两种定义搞混了。5.3 边界测试与胜负判断的细节最后说几个边界条件别嫌啰嗦这些细节经常是压死骆驼的最后一根稻草n 1时先手直接取走唯一一堆答案就是a[0]。如果代码里前缀和或 dp 初始化有问题这个用例最容易暴露。n 2时先手必然取较大的那一堆其实不一定因为只有两个选择且双方各拿一堆先手拿哪端都不影响自己最终拿到的总数不对n2 时先手取左端则拿到a[l]取右端则拿到a[r]为了最大当然取大的。这个用例可以检查长度为 2 的转移。如果题目允许糖果数为 0要确认取走 0 糖果是否算一次合法行动。如果算边界和胜负判断里的等于号要格外小心。判断胜负时如果题目问“先手能否获胜”使用dp[0][n-1] * 2 total表示严格获胜如果允许平局也算赢要用。一些题目会把平局单独定义比如“如果平局则后手胜”这时相等的情况归属就差在这一行判断上。最后的最后分享一个我后来养成的习惯看到这类两端取糖果的题先别急着写代码而是先拿一个n 4的小例子在纸上手推一遍 DP 表。不需要推多大4 个数的表也就 10 个状态几分钟就能填完。这一步能帮你确认状态定义和转移方程是否符合直觉也能在代码出问题时让你有个“标准答案”可以用来对照。还有一个实操小技巧把区间和单独封装成一个range_sum(l, r)函数而不是在代码各处散落pre[r1] - pre[l]。看似多了一次函数调用但调试的时候你能在函数里打日志、加断言可读性和可维护性都会好很多。我教过很多刚开始学区间 DP 的朋友他们最容易犯的错误反而不是算法不会而是这些“细碎但致命”的实现细节。这个题如果完整拿下了后面再遇到“拿石子”“预测赢家”甚至是合并糖果的变体你都会觉得像是在和老朋友打招呼。