877. 石子游戏

题目描述

偶数堆石子排成一行，第 i 堆有 piles[i] 颗，每堆至少 1 颗，石子总数是奇数，因此不会平局。

Alice 和 Bob 轮流行动，Alice 先手。每一回合，当前玩家从这一行的最左端或最右端拿走一整堆。所有石子堆都被拿完后，手中石子总数更多的一方获胜。

假设双方都采取最优策略。Alice 获胜返回 true，Bob 获胜返回 false。

示例 1

输入：piles = [5,3,4,5]
输出：true

解释：Alice 先拿左端的 5，无论 Bob 怎么拿，Alice 最后都能拿到更多石子。

示例 2

输入：piles = [3,7,2,3]
输出：true

数据范围

2 <= piles.length <= 500
piles.length 是偶数。
1 <= piles[i] <= 500
sum(piles[i]) 是奇数。

解题思路：区间 DP（先手净胜分）

区间 DP。dp[i][j] 表示只剩 piles[i..j] 时，当前要拿的人能比对手多拿多少（净胜分）。拿左堆得 piles[i]，剩下 [i+1..j] 轮到对手，对手净胜 dp[i+1][j]，所以自己净胜 piles[i] - dp[i+1][j]；拿右堆同理。取两者最大。按区间长度从小到大填表，答案是 dp[0][n-1] > 0。（数学上可证先手必胜，但 DP 做法可以推广到任意堆数。）

为什么正确

dp[i][j] = 双方最优时，对区间 [i..j] 先手方的石子数减去后手方的石子数。

复杂度分析

时间 O(n²)，空间 O(n²)。

易错点

状态必须是“当前轮到的人”的净胜分，而不是固定为 Alice 的得分，这样转移才能写成“拿走的减去对手的净胜分”。填表顺序要按区间长度，保证用到的小区间已算好。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        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 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 length = 2; length <= n; length++) {
            for (int i = 0; i + length <= n; i++) {
                int j = i + length - 1;
                dp[i][j] = Math.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 length = 2; length <= n; length++) {
            for (int i = 0; i + length <= n; i++) {
                int 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;
    }
};

func stoneGame(piles []int) bool {
	n := len(piles)
	dp := make([][]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([]int, n)
		dp[i][i] = piles[i]
	}
	for length := 2; length <= n; length++ {
		for i := 0; i+length <= n; i++ {
			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
}

var stoneGame = function(piles) {
    const n = piles.length;
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = 0; i < n; i++) {
        dp[i][i] = piles[i];
    }
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i + length <= n; i++) {
            const j = i + length - 1;
            dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] > 0;
};

function stoneGame(piles: number[]): boolean {
    const n = piles.length;
    const dp = Array.from({ length: n }, () => new Array<number>(n).fill(0));
    for (let i = 0; i < n; i++) {
        dp[i][i] = piles[i];
    }
    for (let length = 2; length <= n; length++) {
        for (let i = 0; i + length <= n; i++) {
            const j = i + length - 1;
            dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
        }
    }
    return dp[0][n - 1] > 0;
}

载入编辑器，自己跑一遍 →

其他解法

区间 DP 是博弈类题目的通用工具，对任意堆数都适用；数学结论利用本题的特殊条件一步得到答案。

解法 2：奇偶下标策略（数学结论）时间 O(1)，空间 O(1)

石子堆数是偶数，把下标分成奇数组和偶数组。先手每次都能控制自己只拿同一组：开局两端下标一奇一偶，先手拿走某组一端后，留给对手的两端都属于另一组；对手拿完一端，又露出先手那组的一端。石子总数是奇数，两组之和不可能相等，先手选和更大的那组就必胜，所以直接返回 true。

O(1) 且给出了具体必胜策略，但完全依赖“堆数为偶数、总和为奇数”这两个特殊条件。题目稍有变化（如石子游戏 II、预测赢家）就必须回到区间 DP。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

class Solution {
    public boolean stoneGame(int[] piles) {
        return true;
    }
}

class Solution {
public:
    bool stoneGame(vector<int>& piles) {
        return true;
    }
};

func stoneGame(piles []int) bool {
	return true
}

var stoneGame = function(piles) {
    return true;
};

function stoneGame(piles: number[]): boolean {
    return true;
}

动态规划专题的其他题目

查看动态规划全部题目 →