石子游戏 图解题解

两人都绝顶聪明，石子游戏到底在算什么

一排石子堆 piles，堆数偶数、总数奇数。Alice 和 Bob 轮流从最左或最右整堆拿一堆，Alice 先手，两人都绝顶聪明、只走对自己最有利的一端，问 Alice 最后能不能拿得严格多于 Bob。以 piles=[5,3,4,5] 为例答案是 true。

把所有拿法的博弈树全摊开，为什么会爆炸

每步都有拿左端、拿右端两个分叉，走到底博弈树随堆数指数级膨胀，堆数一多就摊不开。而且对手也绝顶聪明，轮到他会挑对自己最有利的一端，所以我这步好坏取决于剩下那段里对手能占多少便宜。同一段石子被反复重算，把每段结果存下来复用就是动态规划（简称 DP，每段石子的先手净胜分算一次存 dp[i][j]）。

不记两人各拿多少，只记一个「净胜分」

与其分别记 Alice、Bob 各拿多少，不如只记一个净胜分：当前轮到谁取谁就是先手，净胜分是他能领先对手多少，一个差值就把两人的账合成一笔。定义 dp[i][j]——第 i 到第 j 堆这段（i、j 从 0 数起，i 左端、j 右端）里先手能比对手多拿的石子数。整排答案落在 dp[0][n-1]（n 是堆数），大于 0 即先手净赢。

拿一端，为什么要减去对手在剩下那段的净胜分

轮到我取 [i, j] 段，两种拿法。拿左端 piles[i]，剩 [i+1, j] 归对手，他那段净胜分 dp[i+1][j] 是领先我的、要减掉，走左端我净胜 piles[i]−dp[i+1][j]；拿右端得 piles[j]−dp[i][j-1]。

两条路挑更好的，dp[i][j]=max(piles[i]−dp[i+1][j], piles[j]−dp[i][j-1])。这个减号看着别扭却实在：剩下那段的 dp 站在对手视角算，一减就把「对手也会最优应对」自动算进去，符号一翻攻守对调。地基是单堆 dp[i][i]=piles[i]。

拿 piles=[5,3,4,5] 把整张表填出来

先铺单堆地基 dp[0][0]=5、dp[1][1]=3、dp[2][2]=4、dp[3][3]=5。再填长度 2 的区间：dp[0][1]=max(5−3, 3−5)=2；dp[1][2]=max(3−4, 4−3)=1；dp[2][3]=max(4−5, 5−4)=1。

长度 3：dp[0][2]=max(5−dp[1][2], 4−dp[0][1])=max(5−1, 4−2)=4；dp[1][3]=max(3−1, 5−1)=4。整段 dp[0][3]=max(5−4, 5−4)=1，大于 0，先手净赢、返回 true，和示例对上。

先填 dp[0][1] 而不按区间长度，整张表为什么会连环错

这题最致命的坑是填表顺序：dp[i][j] 要用 dp[i+1][j] 和 dp[i][j-1] 这两个短一格的区间，必须先填完短的。若先填 dp[0][1]，它要的 dp[1][1] 还没算、读到初始值 0，整张表一路错下去，所以外层循环一定按区间长度从短到长——这就是区间 DP（大区间由小区间拼出来的动态规划）。复杂度时间与空间都 O(n²)，可滚成一维把空间降到 O(n)。

Python

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

C++

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;
    }
};

Java

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;
    }
}