说实话，我第一次看到“拿糖果”这道题的时候，差点把它当成热身题给秒了。题面本身非常朴素：有 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 还是右端的 3，100 都还留在场上，而下一轮先手就能拿走 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]。
拿完之后发生什么？如果取左端，剩下的区间是[l+1, 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]。 - 对手接下来在区间
[l+1, r]先手，按照dp的定义，对手最多能拿到dp[l+1][r]。 - 区间
[l, r]的总糖果数是固定的sum(l, r)，其中对手拿走的至多是dp[l+1][r]，那么剩下的糖果最终都会归当前玩家所有。 - 所以当前玩家的总收益是：
a[l] + (sum(l+1, r) - dp[l+1][r]) = sum(l, r) - dp[l+1][r]如果当前玩家取右端a[r]，同理收益是：
sum(l, r) - dp[l][r-1]当前玩家会在这两个方案里选更大的那个，因此：
dp[l][r] = max( sum(l, r) - dp[l+1][r], sum(l, r) - dp[l][r-1] )由于两项都包含相同的sum(l, r)，进一步化简为：
dp[l][r] = sum(l, r) - min(dp[l+1][r], dp[l][r-1])这个形式非常清爽：当前玩家的最优收益，等于整个区间糖果总和，减去留给对手的那个子区间里“对手能拿到的最小最优收益”。
这里有个值得停下来想一想的点：min(dp[l+1][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] | 110 | 110 - min(dp[1][1]=100, dp[0][0]=10) = 100 |
| [1,2] | 103 | 103 - min(dp[2][2]=3, dp[1][1]=100) = 100 |
| [2,3] | 12 | 12 - min(dp[3][3]=9, dp[2][2]=3) = 9 |
长度为 3：
| 区间 | 总和 | 计算结果 |
|---|---|---|
| [0,2] | 113 | 113 - min(dp[1][2]=100, dp[0][1]=100) = 13 |
| [1,3] | 112 | 112 - min(dp[2][3]=9, dp[1][2]=100) = 103 |
长度为 4：
dp[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(l+1, 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[l+1][r]和dp[l][r-1]，它们的区间长度都是length - 1。如果先枚举左端点l，再枚举右端点r，比如写成：
for l in range(n): for r in range(l, n): ...那么计算dp[l][r]时，dp[l+1][r]里的l+1比当前的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[l+1][r], a[r] - net[l][r-1])两种定义都能做，但千万别混用。如果你看到别人的代码里dp[l][r] = max(a[l] - dp[l+1][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[l+1][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时，先手必然取较大的那一堆？其实不一定，因为只有两个选择且双方各拿一堆，先手拿哪端都不影响自己最终拿到的总数？不对，n=2 时先手取左端则拿到a[l]，取右端则拿到a[r]，为了最大当然取大的。这个用例可以检查长度为 2 的转移。- 如果题目允许糖果数为 0，要确认取走 0 糖果是否算一次合法行动。如果算，边界和胜负判断里的等于号要格外小心。
- 判断胜负时，如果题目问“先手能否获胜”，使用
dp[0][n-1] * 2 > total表示严格获胜；如果允许平局也算赢，要用>=。一些题目会把平局单独定义，比如“如果平局则后手胜”，这时相等的情况归属就差在这一行判断上。
最后的最后，分享一个我后来养成的习惯：看到这类两端取糖果的题，先别急着写代码，而是先拿一个n = 4的小例子在纸上手推一遍 DP 表。不需要推多大，4 个数的表也就 10 个状态，几分钟就能填完。这一步能帮你确认状态定义和转移方程是否符合直觉，也能在代码出问题时让你有个“标准答案”可以用来对照。
还有一个实操小技巧：把区间和单独封装成一个range_sum(l, r)函数，而不是在代码各处散落pre[r+1] - pre[l]。看似多了一次函数调用，但调试的时候你能在函数里打日志、加断言，可读性和可维护性都会好很多。我教过很多刚开始学区间 DP 的朋友，他们最容易犯的错误反而不是算法不会，而是这些“细碎但致命”的实现细节。这个题如果完整拿下了，后面再遇到“拿石子”“预测赢家”甚至是合并糖果的变体，你都会觉得像是在和老朋友打招呼。
