第六章 - 高频考题(困难)
1872. 石子游戏 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^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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。