What is the key pattern for solving Stone Game III?

The key pattern is state transition dynamic programming, which helps evaluate the optimal moves for Alice and Bob based on the remaining stones.

How does the minmax game theory apply to this problem?

In Stone Game III, Alice tries to maximize her score while Bob attempts to minimize it, which can be represented by a minmax game where each player makes optimal moves.

How can memoization improve the solution?

Memoization stores intermediate results in a DP table, avoiding redundant calculations and improving time efficiency for large input sizes.

What happens if both players have the same score?

If Alice and Bob have the same score at the end of the game, the result is a tie.

How can I optimize the solution for larger inputs?

To optimize the solution for larger inputs, use dynamic programming with memoization to avoid recalculating results for the same game states.

#1406

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

石子游戏 III

Alice 和 Bob 继续他们的石子游戏。几堆石子排成一行，每堆石子都对应一个得分，由数组 stoneValue 给出。 Alice 和 Bob 轮流取石子， Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子。比赛一直持续到所有石头都被拿走。…

数组数学动态规划博弈论

题目描述

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

提示：

1 <= stoneValue.length <= 5 * 10⁴
-1000 <= stoneValue[i] <= 1000

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i)$ ，表示当前玩家在 $[i, n)$ 范围内进行游戏时，可以获得的最大得分差值。如果 $dfs(0) \gt 0$ ，则表示先手玩家 Alice 可以获胜；如果 $dfs(0) \lt 0$ ，则表示后手玩家 Bob 可以获胜；否则，表示两人打成平局。

函数 $dfs(i)$ 的执行逻辑如下：

如果 $i \geq n$ ，说明当前没有石子可以拿了，直接返回 $0$ 即可；
否则，我们枚举当前玩家拿走前 $j+1$ 堆石子，其中 $j \in \{0, 1, 2\}$ ，那么另一个玩家在下一轮可以获得的得分差值为 $dfs(i + j + 1)$ ，从而当前玩家可以获得的得分差值为 $\sum_{k=i}^{i+j} stoneValue[k] - dfs(i + j + 1)$ 。我们要使得当前玩家的得分差值最大，因此可以用 $\max$ 函数得到最大得分差值，即：

dfs(i) = \max_{j \in \{0, 1, 2\}} \left\{\sum_{k=i}^{i+j} stoneValue[k] - dfs(i + j + 1)\right\}

为了防止重复计算，我们可以使用记忆化搜索。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是石子的堆数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            ans, s = -inf, 0
            for j in range(3):
                if i + j >= n:
                    break
                s += stoneValue[i + j]
                ans = max(ans, s - dfs(i + j + 1))
            return ans

        n = len(stoneValue)
        ans = dfs(0)
        if ans == 0:
            return 'Tie'
        return 'Alice' if ans > 0 else 'Bob'

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for an understanding of dynamic programming and game theory concepts.
question_mark
Ensure the candidate can map the problem to a minmax game scenario.
question_mark
Assess the candidate’s ability to optimize a recursive solution using memoization.

warning

常见陷阱

外企场景

error
Overlooking the optimal move for Bob and Alice, which can lead to incorrect strategies.
error
Failing to implement memoization properly, leading to inefficient solutions.
error
Misunderstanding the draw condition, which might lead to wrong outputs when the game ends in a tie.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the game rules by allowing the player to choose more than 3 stones per turn.
arrow_right_alt
Introduce multiple players (e.g., 3 players) instead of just Alice and Bob.
arrow_right_alt
Alter the game so that one player’s goal is to minimize their own score rather than the opponent's score.

help

常见问题

外企场景

继续练习

#1563 石子游戏 V #1140 石子游戏 II #1690 石子游戏 VII