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
- 动态规划
- 前缀和
- 暂无
看下数据范围是
首先我们需要观察到：游戏从始到终的石子值总和是不变的，因此每次玩家选择拿前 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 数组的开销，转而使用一个变量即可。
- 语言支持：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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
