LeetCode 题解工作台
石子游戏
Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子， 排成一行 ；每堆都有 正 整数颗石子，数目为 piles[i] 。 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。 Alice 和 Bob 轮流进行， Alice 先开始 。 每回合，玩家从行的 开始 或 结…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们设计一个函数 $dfs(i, j)$，表示从第 堆石子到第 堆石子，当前玩家与另一个玩家的石子数量之差的最大值。那么答案就是 $dfs(0, n - 1) \gt 0$。 函数 $dfs(i, j)$ 的计算方法如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。
Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。
假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。
示例 1：
输入：piles = [5,3,4,5] 输出：true 解释： Alice 先开始，只能拿前 5 颗或后 5 颗石子 。 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。 如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。 如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。
示例 2：
输入：piles = [3,7,2,3] 输出：true
提示：
2 <= piles.length <= 500piles.length是 偶数1 <= piles[i] <= 500sum(piles[i])是 奇数
解题思路
方法一：记忆化搜索
我们设计一个函数 ，表示从第 堆石子到第 堆石子，当前玩家与另一个玩家的石子数量之差的最大值。那么答案就是 。
函数 的计算方法如下：
- 如果 ，说明当前没有石子了，所以当前玩家没有石子可以拿，差值为 ，即 。
- 否则，当前玩家有两种选择，如果选择第 堆石子，那么当前玩家与另一个玩家的石子数量之差为 ；如果选择第 堆石子，那么当前玩家与另一个玩家的石子数量之差为 。当前玩家会选择两种情况中差值较大的情况，也就是说 。
最后，我们只需要判断 即可。
为了避免重复计算，我们可以使用记忆化搜索的方法，用一个数组 记录所有的 的值，当函数再次被调用到时，我们可以直接从 中取出答案而不需要重新计算。
时间复杂度 ，空间复杂度 。其中 是石子的堆数。
class Solution:
def stoneGame(self, piles: List[int]) -> bool:
@cache
def dfs(i: int, j: int) -> int:
if i > j:
return 0
return max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1))
return dfs(0, len(piles) - 1) > 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N^2) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for understanding of dynamic programming with state transitions.
- question_mark
Check if the candidate can explain how optimal substructure applies to the problem.
- question_mark
Evaluate the candidate’s ability to optimize both time and space complexity.
常见陷阱
外企场景- error
Not recognizing the optimal substructure and solving the problem by brute force.
- error
Incorrectly calculating the value for subarrays due to not considering both player's moves.
- error
Overcomplicating the space complexity by using unnecessary data structures.
进阶变体
外企场景- arrow_right_alt
Consider variations where players may have different strategies or time constraints.
- arrow_right_alt
Test variations with different sizes of input to evaluate how well the solution scales.
- arrow_right_alt
Explore how the problem behaves if the total number of stones is even, requiring ties to be handled.