1872. 石子游戏 VIII

题目地址(1872. 石子游戏 VIII)

https://leetcode-cn.com/problems/stone-game-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^5
-10^4 <= stones[i] <= 10^4

前置知识

• 动态规划

• 前缀和

公司

• 暂无

前缀和 + 暴力枚举记忆化递归（n^2 时间复杂度）

思路

看下数据范围是 $10^5$， 这意味着 $n^2$ 不可行，不过我仍然想先从暴力解法开始，帮助大家理清思路。

首先我们需要观察到：游戏从始到终的石子值总和是不变的，因此每次玩家选择拿前 x 的时候， 得到的分数一定是原始石子数组的前缀和。因此不难想到使用前缀和加速分数的计算。

接下来，我们尝试模拟游戏的进行。

• 刚开始，alice 可以选择前 x 项，其中 1 < x <= n，得到 pres[x] 的分数，其中 pres 为原数组的前缀和。

• 接下来，bob 也可以选择前 x 项，其中 x < x' <= n - x，得到 pres[x'] 的分数。

• 。。。

我们可以使用递归来模拟 alice 和 bob 交替决策的过程，用 for 循环模拟取前 x 项的过程，并使用记忆化来保存中间过程以避免重复计算。

关键点

• 前缀和

• 动态规划

代码

• 语言支持：Python3

Python3 Code:

from itertools import accumulate

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        pres = list(accumulate(stones))

        @cache
        def dp(pos):
            if pos == len(stones):
                return 0
            ans = float("-inf")
            for nxt in range(pos, len(stones)):
                ans = max(ans, pres[nxt] - dp(nxt + 1))
            return ans

        return dp(1)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(n)$

优化记忆化递归

思路

上面是简单的模拟。

实际上，我们可以进行一个优化。使用 dp(i) 表示还剩下 [i, n) 要选择的情况下，Alice 所能得到的最大分数差。

对于某个玩家来说，其对应决策可以分为两种：

• 选取当前数及之前的所有数（等价于 pres[pos]，其中 pos 为上个玩家选完后的下个位置），那么 dp[i] = pres[i] - dp[i+1]。

这是因为 bob 也会最大化发挥。

• 不选择当前数（可能选下一个，下下一个。。。 etc），那么 dp[i] = dp[i + 1]

代码

• 语言支持：Python3

Python3 Code:

from itertools import accumulate


class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        pres = list(accumulate(stones))
        n = len(stones)

        @cache
        def dp(pos):
            if pos == n - 1:
                return pres[n - 1]
            return max(dp(pos + 1), pres[pos] - dp(pos + 1))

        return dp(1)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

DP + 滚动数组优化

思路

将代码改造为 dp 也不难。

当你改造为了 dp，顺便也可以进行一个小小的优化，那就是使用滚动数组，节省了 dp 数组的开销，转而使用一个变量即可。

代码

• 语言支持：Python3

Python3 Code:

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

滚动数组优化：

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

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$。虽然没有使用 dp 数组，但是 pres 数组的空间仍然存在。

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。