石子游戏 VIII

1872. 石子游戏 VIII

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

选择一个整数 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⁵
-10⁴ <= stones[i] <= 10⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int stoneGameVIII(vector<int>& stones) { } };

golang 解法, 执行用时: 160 ms, 内存消耗: 8.8 MB, 提交时间: 2023-08-18 14:48:14

func stoneGameVIII(stones []int) int {
    n := len(stones)
    s := 0
    for _, stone := range stones {
        s += stone
    }
    res := s
    for i := n-1; i >= 2; i-- {
        s -= stones[i]
        res = max(res, s - res)
    }
    return res
}

func max(a, b int) int { if a > b { return a }; return b }

python3 解法, 执行用时: 216 ms, 内存消耗: 27.8 MB, 提交时间: 2023-08-18 14:46:31

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        s = sum(stones)
        res = s
        for i in range(n-1, 1, -1):
            s -= stones[i]
            res = max(res, s - res)
        return res

php 解法, 执行用时: 324 ms, 内存消耗: 31 MB, 提交时间: 2023-08-18 14:44:55

class Solution {

    /**
     * @param Integer[] $stones
     * @return Integer
     */
    function stoneGameVIII($stones) {
        $n = count($stones);
        $sum = 0;
        for($i = 0; $i < $n; $i++){
            $sum += $stones[$i];
        }

        $res = $sum;

        for($i = $n - 1; $i >= 2; $i--){
            $sum -= $stones[$i];
            $res = max($res, $sum - $res);
        }
        return $res;
    }
}

java 解法, 执行用时: 2 ms, 内存消耗: 56.2 MB, 提交时间: 2023-08-18 14:43:08

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += stones[i];
        }

        int res = sum;

        for(int i = n - 1; i >= 2; i--){
            sum -= stones[i];
            res = Math.max(res, sum - res);
        }
        return res;
    }
}

java 解法, 执行用时: 5 ms, 内存消耗: 58.8 MB, 提交时间: 2023-08-18 14:42:07

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] sum = new int[n + 1];
        for(int i = 0; i < n; i++){
            sum[i + 1] = sum[i] + stones[i];
        }

        int[] dp = new int[n + 1];  // dp[i] 
        dp[n] = sum[n];

        for(int i = n - 1; i >= 2; i--){
            dp[i] = Math.max(dp[i + 1], sum[i] - dp[i + 1]);
        }
        return dp[2];
    }
}

java 解法, 执行用时: 44 ms, 内存消耗: 74.1 MB, 提交时间: 2023-08-18 14:40:04

class Solution {

    int n;
    int[] stones;
    int[] sum;
    Integer[] memo;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        
        memo = new Integer[n + 1];
        sum = new int[n + 1];

        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        memo[n] = sum[n];
        return solve(2);
    }

    public int solve(int idx) {
        if(memo[idx] != null) return memo[idx];

        int res = Math.max(solve(idx + 1), sum[idx] - solve(idx + 1));
        return memo[idx] = res;
    }
}

上一题

下一题

详情