题目描述
思路解析动画文字版
笨办法是把所有拿法的树全展开，指数级爆炸。关键卡点是：轮到对手时，对手也按最优走，所以我这一步的好坏，取决于「剩下那段」对手能占多少便宜。
不去分别记 Alice/Bob 各多少，而是记一个净胜分=先手领先后手多少。最后只要看整段 [0, n-1] 的净胜分是不是大于 0，大于 0 就是先手赢。
我从左端拿 piles[i]，剩 [i+1, j] 轮到对手，对手在那段的净胜分是 dp[i+1][j]，那是他领先我的，得减掉。拿右端同理。两种拿法取较大的那个。
把石子堆摆出来：这就是要玩的四堆石子。下面我们要建一张二维表 dp[i][j]，行号 i 是区间左端，列号 j 是区间右端，先把所有「单堆」小区间填好，再逐步拼大。
建表 · dp[i][j] = 区间[i,j]先手净胜分：表里只有右上三角(i≤j)有意义——左端不能超过右端。我们先填主对角线(长度 1 的区间)，再一条条往右上方的对角线推。
对角线 · 单堆 dp[0][0]：区间只剩一堆 [0,0] 时，先手直接整堆拿走、对手啥都没有，净胜分就是这堆本身 5。这是不依赖别人的地基。
对角线 · 单堆 dp[1][1]：同理 [1,1] 只剩第 1 堆，先手净胜 3。主对角线上每一格都等于那一堆自己的石子数。
对角线 · 单堆 dp[2][2]：[2,2] 填 4。对角线一格一格往下推，把每堆单独的「净胜分地基」铺满。
对角线填完 · dp[3][3]：主对角线铺满：5、3、4、5。地基齐了，接下来填长度 2 的区间——它们要靠刚填好的单堆来推。
长度2 · 看 dp[0][1] 的两个来源：填 dp[0][1] 前先锁定它依赖谁:拿左端 5 就要用右下那格 dp[1][1],拿右端 3 就要用左下那格 dp[0][0]。两个来源都已经填好了,可以算。
长度2 · 填 dp[0][1]：区间 [0,1]:拿左端 5、剩 [1,1] 给对手(他净胜 dp[1][1]=3)→ 5−3=2;拿右端 3、剩 [0,0] 给对手(他净胜 5)→ 3−5=−2。取大,dp[0][1]=2:先手拿大堆 5 领先 2。
长度2 · 看 dp[1][2] 的两个来源：下一格 dp[1][2]:拿左端 3 看 dp[2][2],拿右端 4 看 dp[1][1]。两个来源都在对角线上、已就绪。
长度2 · 填 dp[1][2]：区间 [1,2]:拿左端 3 → 3−dp[2][2](=4)=−1;拿右端 4 → 4−dp[1][1](=3)=1。先手该拿那堆 4,领先 1。dp[1][2]=1。
长度2 · 看 dp[2][3] 的两个来源：最后一个长度 2 区间 dp[2][3]:拿左端 4 看 dp[3][3],拿右端 5 看 dp[2][2]。来源就绪,开算。
长度2 · 填 dp[2][3]：区间 [2,3]:拿左端 4 → 4−5=−1;拿右端 5 → 5−4=1。先手拿大堆 5,领先 1。长度 2 的三个区间全部就绪。
长度3 · 看 dp[0][2] 的两个来源：进到长度 3。填 dp[0][2] 要用长度 2 的两格:拿左端 5 看 dp[1][2],拿右端 4 看 dp[0][1]。它们上一轮刚填完,正好能用。
长度3 · 填 dp[0][2]：区间 [0,2]:拿左端 5、剩 [1,2](对手净胜 dp[1][2]=1)→ 5−1=4;拿右端 4、剩 [0,1](对手净胜 2)→ 4−2=2。取大,dp[0][2]=4:先拿左端那堆 5 最划算。
长度3 · 看 dp[1][3] 的两个来源：另一个长度 3 区间 dp[1][3]:拿左端 3 看 dp[2][3],拿右端 5 看 dp[1][2]。两个来源就绪。
长度3 · 填 dp[1][3]：区间 [1,3]:拿左端 3、剩 [2,3](对手净胜 1)→ 3−1=2;拿右端 5、剩 [1,2](对手净胜 1)→ 5−1=4。先拿右端那堆 5,领先 4。dp[1][3]=4。
长度4 · 填 dp[0][3] 答案格：整段 [0,3]:拿左端 5、剩 [1,3](对手净胜 dp[1][3]=4)→ 5−4=1;拿右端 5、剩 [0,2](对手净胜 4)→ 5−4=1。两种都领先 1,dp[0][3]=1。
填表完成 · 读答案：右上角 dp[0][3]=1 就是整排石子的先手净胜分,大于 0 → Alice 严格多拿,返回 true。和示例答案对上了。
回看 · 答案怎么拼出来的：顺着箭头回看:右上角答案是一层层从短区间拼上来的——单堆 → 长度2 → 长度3 → 整段。这就是区间 DP「小问题搭大问题」的全貌。
区间 DP 的威力:把「双方都最优」的博弈,变成一张表里从小区间拼大区间的填格子,每格只看相邻两格,线性平方搞定。
雷区实演 · 顺序错就读到空格：如果不按区间长度、而是顺手先填 dp[0][1],它依赖的 dp[1][1] 这格还没算,读到的是初始 0,整张表就连环错下去。先短后长才能保证依赖项就绪。
边界三连：本题有个数学结论:偶数堆+奇数总数下先手必胜(可直接 return true)。但区间 DP 是通用解,换成「净胜分多少」「奇数堆」等变体照样能算。
面试追问：「能 return true 但要会写通用 DP」是这题最漂亮的回答:既知道结论,又能给出可推广的算法。
参考代码
class Solution: def stoneGame(self, piles): n = len(piles) dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = piles[i] # 单堆地基 for length in range(2, n + 1): # 区间从短到长 for i in range(n - length + 1): j = i + length - 1 dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) return dp[0][n-1] > 0复杂度
- 时间复杂度：O(n²)，二维表共 n² 个格子,每格 O(1) 转移(只看相邻两格)
- 空间复杂度：O(n²)，dp 二维表;可优化成一维滚动数组降到 O(n)
易错点
面试追问把动画讲成自己的话
追问本题可以直接 return true 吗,为什么?
追问如果石子堆数可能是奇数、不保证先手必胜呢?
追问能否把空间优化到 O(n)?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
骑士拨号器
LeetCode 935 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题