Hard

题目描述

Alice 和 Bob 继续他们的石子游戏。几块石子 排成一行，每块石子都有一个关联的数值，该数值由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的前 1，2，或 3 块石子。

每个玩家的得分为他拿到的石子的数值总和。每个玩家的初始分数都是 0。

游戏的目标是结束时分数最高，分数最高的一方获胜。如果两个玩家的分数相同，那么这局游戏平局。游戏继续进行，直到所有石子都被拿走。

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

如果 Alice 会获胜就返回 "Alice"，Bob 获胜则返回 "Bob"，平局则返回 "Tie"。

示例 1：

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

示例 2：

输入：stoneValue = [1,2,3,-9]
输出："Alice"
解释：Alice 必须在第一步选择所有三堆才能获胜，给 Bob 留下负分。
如果 Alice 选择一堆，她的分数将是 1，下一步 Bob 的分数变成 5。在下一步中，Alice 将拿走值为 -9 的堆并败北。
如果 Alice 选择两堆，她的分数将是 3，下一步 Bob 的分数变成 3。在下一步中，Alice 将拿走值为 -9 的堆，也会败北。
记住两人都采用最优策略，所以 Alice 会选择能让她获胜的方案。

示例 3：

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

提示：

  • 1 <= stoneValue.length <= 5 * 10^4
  • -1000 <= stoneValue[i] <= 1000

解题思路

解题思路

这是一个典型的博弈论动态规划问题。我们需要考虑双方都采用最优策略的情况。

核心思想

  1. 相对得分思维：与其分别计算 Alice 和 Bob 的得分，不如计算他们的相对得分差值
  2. 状态定义：dp[i] 表示从位置 i 开始到游戏结束，当前玩家相对于对手能获得的最大得分差
  3. 状态转移：当前玩家可以选择拿走 1、2 或 3 块石子，每种选择都会影响后续的相对得分

递推关系

对于位置 i，当前玩家有三种选择：

  • 拿 1 块石子：得分为 sum[i]，剩余部分对手先手，相对得分差为 sum[i] - dp[i+1]
  • 拿 2 块石子：得分为 sum[i] + sum[i+1]，相对得分差为 sum[i] + sum[i+1] - dp[i+2]
  • 拿 3 块石子：得分为 sum[i] + sum[i+1] + sum[i+2]，相对得分差为 sum[i] + sum[i+1] + sum[i+2] - dp[i+3]

当前玩家会选择能使自己相对得分最大的策略，所以： dp[i] = max(三种选择的相对得分差)

实现要点

  1. 从后往前计算，因为后面的状态会影响前面的决策
  2. 边界处理：当剩余石子少于选择数量时，只能拿完所有剩余石子
  3. 最终判断：dp[0] 就是 Alice 相对于 Bob 的得分差，根据正负性判断胜负

代码实现

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> dp(n + 3, 0);  // dp[i] 表示从位置i开始，当前玩家相对对手的最大得分差
        
        // 从后往前计算
        for (int i = n - 1; i >= 0; i--) {
            int take = 0;
            dp[i] = INT_MIN;
            // 尝试拿1、2、3块石子
            for (int k = 1; k <= 3 && i + k - 1 < n; k++) {
                take += stoneValue[i + k - 1];
                dp[i] = max(dp[i], take - dp[i + k]);
            }
        }
        
        if (dp[0] > 0) return "Alice";
        else if (dp[0] < 0) return "Bob";
        else return "Tie";
    }
};

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [0] * (n + 3)  # dp[i] 表示从位置i开始，当前玩家相对对手的最大得分差
        
        # 从后往前计算
        for i in range(n - 1, -1, -1):
            take = 0
            dp[i] = float('-inf')
            # 尝试拿1、2、3块石子
            for k in range(1, 4):
                if i + k - 1 < n:
                    take += stoneValue[i + k - 1]
                    dp[i] = max(dp[i], take - dp[i + k])
        
        if dp[0] > 0:
            return "Alice"
        elif dp[0] < 0:
            return "Bob"
        else:
            return "Tie"

public class Solution {
    public string StoneGameIII(int[] stoneValue) {
        int n = stoneValue.Length;
        int[] dp = new int[n + 3];  // dp[i] 表示从位置i开始，当前玩家相对对手的最大得分差
        
        // 从后往前计算
        for (int i = n - 1; i >= 0; i--) {
            int take = 0;
            dp[i] = int.MinValue;
            // 尝试拿1、2、3块石子
            for (int k = 1; k <= 3 && i + k - 1 < n; k++) {
                take += stoneValue[i + k - 1];
                dp[i] = Math.Max(dp[i], take - dp[i + k]);
            }
        }
        
        if (dp[0] > 0) return "Alice";
        else if (dp[0] < 0) return "Bob";
        else return "Tie";
    }
}

var stoneGameIII = function(stoneValue) {
    const n = stoneValue.length;
    const dp = new Array(n + 3).fill(0);  // dp[i] 表示从位置i开始，当前玩家相对对手的最大得分差
    
    // 从后往前计算
    for (let i = n - 1; i >= 0; i--) {
        let take = 0;
        dp[i] = -Infinity;
        // 尝试拿1、2、3块石子
        for (let k = 1; k <= 3 && i + k - 1 < n; k++) {
            take += stoneValue[i + k - 1];
            dp[i] = Math.max(dp[i], take - dp[i + k]);
        }
    }
    
    if (dp[0] > 0) return "Alice";
    else if (dp[0] < 0) return "Bob";
    else return "Tie";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个位置计算常数次（最多3次选择）
空间复杂度O(n) - 需要dp数组存储状态

相关题目