1563：石子游戏 V（2087 分）

力扣第 203 场周赛第 4 题

题目

几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。

游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

提示：

• 1 <= stoneValue.length <= 500
• 1 <= stoneValue[i] <= 10^6

分析

#1

依然考虑递归。令辅助函数 help(A) 代表在数组 A 玩游戏 Alice 能得到的最大分数。

假设 Alice 在 i 处分割，即分为 A[:i] 和 A[i:]，根据两个子数组的和的大小，可转为不同的递归子问题。

若 sum(A[:i]) < sum(A[i:])，此时 Alice 能获得的最大分数为 sum(A[:i])+help(A[:i])

若 sum(A[:i]) > sum(A[i:])，此时 Alice 能获得的最大分数为 sum(A[i:])+help(A[i:])

若 sum(A[:i]) == sum(A[i:])，此时 Alice 能获得的最大分数为 sum(A[:i])+max(help(A[:i]),help(A[i:]))

遍历 i 取最大值即可

其中 A 的前缀和、后缀和可以递推得到

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def stoneGameV(self, stoneValue: List[int]) -> int:
	@lru_cache(None)
	def help(A):
		if len(A) == 1:
			return 0
		res, pre, suf = 0, 0, sum(A)
		for i in range(1, len(A)):
			pre += A[i-1]
			suf -= A[i-1]
			if pre < suf:
				res = max(res, pre + help(A[:i]))
			elif pre > suf:
				res = max(res, suf + help(A[i:]))
			else:
				res = max(res, pre + help(A[:i]), suf + help(A[i:]))
		return res

	return help(tuple(stoneValue))

3444 ms

#2

解答