Hard

题目描述

Alice 和 Bob 轮流玩一个游戏，Alice 先开始。

有 n 个石子排成一行。在每个玩家的回合中，当石子数量大于一个时，他们将执行以下操作：

  • 选择一个整数 x > 1，并从行的最左边移除 x 个石子。
  • 将移除的石子值的总和加到玩家的分数中。
  • 在行的左侧放置一个新石子，其值等于移除石子值的总和。

当行中只剩下一个石子时，游戏停止。

Alice 和 Bob 之间的分数差为（Alice 的分数 - Bob 的分数）。Alice 的目标是最大化分数差，Bob 的目标是最小化分数差。

给定一个长度为 n 的整数数组 stones，其中 stones[i] 表示从左边开始第 i 个石子的值，返回如果两人都以最优策略玩游戏，Alice 和 Bob 之间的分数差。

示例 1：

输入：stones = [-1,2,-3,4,-5]
输出：5
解释：
- Alice 移除前 4 个石子，将 (-1) + 2 + (-3) + 4 = 2 加到她的分数中，并在左侧放置一个值为 2 的石子。stones = [2,-5]。
- Bob 移除前 2 个石子，将 2 + (-5) = -3 加到他的分数中，并在左侧放置一个值为 -3 的石子。stones = [-3]。
他们的分数差为 2 - (-3) = 5。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]
输出：13
解释：
- Alice 移除所有石子，将 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 加到她的分数中，并在左侧放置一个值为 13 的石子。stones = [13]。
他们的分数差为 13 - 0 = 13。

示例 3：

输入：stones = [-10,-12]
输出：-22
解释：
- Alice 只能进行一次移动，即移除两个石子。她将 (-10) + (-12) = -22 加到她的分数中，并在左侧放置一个值为 -22 的石子。stones = [-22]。
他们的分数差为 (-22) - 0 = -22。

约束：

  • n == stones.length
  • 2 <= n <= 10^5
  • -10^4 <= stones[i] <= 10^4

解题思路

这是一个博弈论问题，需要用动态规划来解决。

关键观察：

  1. 每次移除操作实际上是从左侧移除连续的石子，然后用它们的和替换
  2. 游戏的状态可以用当前还剩多少个石子来表示
  3. 由于每次都是从左侧操作，我们可以预先计算前缀和

状态定义： 设 dp[i] 表示当前轮到某玩家操作，且还剩下 i 个石子时，该玩家相对于对手能获得的最大分数差。

状态转移： 当前玩家可以选择移除前 j 个石子（其中 j 从 2 到 i），获得分数为前缀和 prefix[j-1]，然后轮到对手操作剩下的 i-j+1 个石子。

转移方程为：dp[i] = max(prefix[j-1] - dp[i-j+1]) 对所有有效的 j

优化： 我们可以从右往左计算，维护一个最大值来避免重复计算，将时间复杂度从 O(n²) 优化到 O(n)。

具体来说，dp[i] = max(dp[i+1], prefix[i-1] - dp[i+1])，其中第一项表示当前玩家选择移除前 2 个石子，第二项表示选择移除前 i 个石子。

代码实现

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefix(n);
        prefix[0] = stones[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1] + stones[i];
        }
        
        int dp = prefix[n-1]; // dp[n] = prefix[n-1]
        for (int i = n-1; i >= 2; i--) {
            dp = max(dp, prefix[i-1] - dp);
        }
        
        return dp;
    }
};

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix = [0] * n
        prefix[0] = stones[0]
        for i in range(1, n):
            prefix[i] = prefix[i-1] + stones[i]
        
        dp = prefix[n-1]  # dp[n] = prefix[n-1]
        for i in range(n-1, 1, -1):
            dp = max(dp, prefix[i-1] - dp)
        
        return dp

public class Solution {
    public int StoneGameVIII(int[] stones) {
        int n = stones.Length;
        int[] prefix = new int[n];
        prefix[0] = stones[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i-1] + stones[i];
        }
        
        int dp = prefix[n-1]; // dp[n] = prefix[n-1]
        for (int i = n-1; i >= 2; i--) {
            dp = Math.Max(dp, prefix[i-1] - dp);
        }
        
        return dp;
    }
}

var stoneGameVIII = function(stones) {
    const n = stones.length;
    const prefix = new Array(n);
    prefix[0] = stones[0];
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i-1] + stones[i];
    }
    
    let dp = prefix[n-1]; // dp[n] = prefix[n-1]
    for (let i = n-1; i >= 2; i--) {
        dp = Math.max(dp, prefix[i-1] - dp);
    }
    
    return dp;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n)
空间复杂度O(n)

其中 n 是石子的数量。时间复杂度为 O(n) 因为我们需要计算前缀和和进行一次动态规划遍历。空间复杂度为 O(n) 用于存储前缀和数组，实际上可以进一步优化到 O(1)。

相关题目