石子游戏 图解题解

这道题到底在问什么

piles

[5,3,4,5]

输出

true

解释

Alice 有必胜策略，最终石子数严格多于 Bob

先想最直接的笨办法

笨办法是把所有拿法的树全展开，指数级爆炸。关键卡点是：轮到对手时，对手也按最优走，所以我这一步的好坏，取决于「剩下那段」对手能占多少便宜。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法是把所有拿法的树全展开，指数级爆炸。关键卡点是：轮到对手时，对手也按最优走，所以我这一步的好坏，取决于「剩下那段」对手能占多少便宜。
2. 4不去分别记 Alice/Bob 各多少，而是记一个净胜分=先手领先后手多少。最后只要看整段 [0, n-1] 的净胜分是不是大于 0，大于 0 就是先手赢。
3. 5我从左端拿 piles[i]，剩 [i+1, j] 轮到对手，对手在那段的净胜分是 dp[i+1][j]，那是他领先我的，得减掉。拿右端同理。两种拿法取较大的那个。
4. 7下标 0~3，值=每堆石子数这就是要玩的四堆石子。下面我们要建一张二维表 dp[i][j]，行号 i 是区间左端，列号 j 是区间右端，先把所有「单堆」小区间填好，再逐步拼大。
5. 8表格待填，行=左端 i，列=右端 j表里只有右上三角(i≤j)有意义——左端不能超过右端。我们先填主对角线(长度 1 的区间)，再一条条往右上方的对角线推。
6. 9只剩一堆 → 先手全拿走区间只剩一堆 [0,0] 时，先手直接整堆拿走、对手啥都没有，净胜分就是这堆本身 5。这是不依赖别人的地基。
7. 10只剩一堆 → 先手全拿走同理 [1,1] 只剩第 1 堆，先手净胜 3。主对角线上每一格都等于那一堆自己的石子数。
8. 11只剩一堆 → 先手全拿走[2,2] 填 4。对角线一格一格往下推，把每堆单独的「净胜分地基」铺满。
9. 12长度 1 的区间全部就绪主对角线铺满：5、3、4、5。地基齐了，接下来填长度 2 的区间——它们要靠刚填好的单堆来推。
10. 13目标格亮起，先看依赖谁填 dp[0][1] 前先锁定它依赖谁:拿左端 5 就要用右下那格 dp[1][1],拿右端 3 就要用左下那格 dp[0][0]。两个来源都已经填好了,可以算。
11. 14区间 [0,1] = 堆 5 与 3区间 [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。
12. 15目标格亮起，先看依赖谁下一格 dp[1][2]:拿左端 3 看 dp[2][2],拿右端 4 看 dp[1][1]。两个来源都在对角线上、已就绪。
13. 16区间 [1,2] = 堆 3 与 4区间 [1,2]:拿左端 3 → 3−dp[2][2](=4)=−1;拿右端 4 → 4−dp[1][1](=3)=1。先手该拿那堆 4,领先 1。dp[1][2]=1。
14. 17目标格亮起，先看依赖谁最后一个长度 2 区间 dp[2][3]:拿左端 4 看 dp[3][3],拿右端 5 看 dp[2][2]。来源就绪,开算。
15. 18区间 [2,3] = 堆 4 与 5区间 [2,3]:拿左端 4 → 4−5=−1;拿右端 5 → 5−4=1。先手拿大堆 5,领先 1。长度 2 的三个区间全部就绪。
16. 19目标格亮起，依赖更短的区间进到长度 3。填 dp[0][2] 要用长度 2 的两格:拿左端 5 看 dp[1][2],拿右端 4 看 dp[0][1]。它们上一轮刚填完,正好能用。
17. 20区间 [0,2] = 堆 5,3,4区间 [0,2]:拿左端 5、剩 [1,2](对手净胜 dp[1][2]=1)→ 5−1=4;拿右端 4、剩 [0,1](对手净胜 2)→ 4−2=2。取大,dp[0][2]=4:先拿左端那堆 5 最划算。
18. 21目标格亮起，依赖更短的区间另一个长度 3 区间 dp[1][3]:拿左端 3 看 dp[2][3],拿右端 5 看 dp[1][2]。两个来源就绪。
19. 22区间 [1,3] = 堆 3,4,5区间 [1,3]:拿左端 3、剩 [2,3](对手净胜 1)→ 3−1=2;拿右端 5、剩 [1,2](对手净胜 1)→ 5−1=4。先拿右端那堆 5,领先 4。dp[1][3]=4。
20. 23整段 [0,3]，靠两个长度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。
21. 24dp[0][3] = 1 > 0 → 先手赢右上角 dp[0][3]=1 就是整排石子的先手净胜分,大于 0 → Alice 严格多拿,返回 true。和示例答案对上了。
22. 25dp[0][3] 来自 dp[1][3]，后者来自 dp[1][2]顺着箭头回看:右上角答案是一层层从短区间拼上来的——单堆 → 长度2 → 长度3 → 整段。这就是区间 DP「小问题搭大问题」的全貌。
23. 26区间 DP 的威力:把「双方都最优」的博弈,变成一张表里从小区间拼大区间的填格子,每格只看相邻两格,线性平方搞定。
24. 30若先算 dp[0][1] 时 dp[1][1] 还没填如果不按区间长度、而是顺手先填 dp[0][1],它依赖的 dp[1][1] 这格还没算,读到的是初始 0,整张表就连环错下去。先短后长才能保证依赖项就绪。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];  // 地基
        for (int len = 2; len <= n; len++) {              // 从短到长
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = max(piles[i] - dp[i+1][j],
                               piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }
};

class Solution {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = piles[i];  // 地基
        for (int len = 2; len <= n; len++) {              // 从短到长
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(piles[i] - dp[i+1][j],
                                    piles[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] > 0;
    }
}

复杂度

面试官可能追问