1872. 石子游戏VIIIJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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(int[] stones) {
        //Alice想要Alice-Bob最大化
        //Bob想要Bob-Alice最小化也就是Alice-Bob最大化
        //所以对于任何一个决策者要达到的目的是一样的 都是想要Alice-Bob在当前决策区间内能够最大化
        //定义dp问题 dp[i]表示当前i~n-1的区间内 Alice-Bob能够达到的最大值
        //dp[i]=Math.max(preSum[i]-dp[i+1],preSum[i+1]-dp[i+2]...preSum[n-2]-dp[n-1])
        //其中preSum(i+1)-dp[i+2]....preSum[n-2]-dp[n-1]=dp[i+1]
        //所以dp[i]=Math.max(preSum[i]-dp[i+1],dp[i+1]);
        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[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];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 总结

分析出几种情况，然后分别对各个情况实现

#Java