Skip to content

Latest commit

 

History

History
126 lines (88 loc) · 4.5 KB

File metadata and controls

126 lines (88 loc) · 4.5 KB

English Version

题目描述

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

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

  1. 选择一个整数 x > 1 ,并且 移除 最左边的 x 个石子。
  2.  移除 的石子价值之  累加到该玩家的分数中。
  3. 将一个 新的石子 放在最左边,且新石子的值为被移除石子值之和。

当只剩下 一个 石子时,游戏结束。

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 <= 105
  • -104 <= stones[i] <= 104

解法

“前缀和 + 动态规划”实现。

每次取走最左边的 x 个石子,把它们的和放回最左边,前缀和 preSum[x] 不变。

假设 dp[i] 表示当 Alice 选择 [i, n) 范围内的某个下标时,Alice 与 Bob 分数的最大差值。

  • 若 Alice 选择 i,她获得的分数是 preSum[i],此时 Bob 会在 [i+1, n] 范围内选择,并且 Bob 也会采取最优策略,此时最大差值为 dp[i+1]。状态转移方程:dp[i] = preSum[i] - dp[i+1]
  • 若 Alice 没选择 i,那么她需要在 [i+1, n) 范围内找,状态转移方程为 dp[i] = dp[i+1]

最优策略下,dp[i] = max(dp[i+1], preSum[i] - dp[i+1])。这里 $O(n)$ 的空间复杂度可以优化为一个变量 f。

x 必须大于 1,所以题目即是求 dp[1]

Python3

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        pre_sum = list(accumulate(stones))
        f = pre_sum[len(stones) - 1]
        for i in range(len(stones) - 2, 0, -1):
            f = max(f, pre_sum[i] - f)
        return f

Java

class Solution {
    public int stoneGameVIII(int[] stones) {
        int n = stones.length;
        int[] preSum = new int[n];
        preSum[0] = stones[0];
        for (int i = 1; i < n; ++i) {
            preSum[i] = preSum[i - 1] + stones[i];
        }
        int f = preSum[n - 1];
        for (int i = n - 2; i > 0; --i) {
            f = Math.max(f, preSum[i] - f);
        }
        return f;
    }
}

...