LeetCode 题解工作台
石子游戏 V
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。 游戏中的每一轮：Alice 会将这行石子分成两个 非空行 （即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们先预处理出前缀和数组 ，其中 表示数组 前 个元素的和。 接下来，我们设计一个函数 $\textit{dfs}(i, j)$，表示数组 中下标范围 $[i, j]$ 内的石子，Alice 能够获得的最大分数。那么答案就是 $\textit{dfs}(0, n - 1)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 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 <= 5001 <= stoneValue[i] <= 106
解题思路
方法一：记忆化搜索 + 剪枝
我们先预处理出前缀和数组 ，其中 表示数组 前 个元素的和。
接下来，我们设计一个函数 ，表示数组 中下标范围 内的石子，Alice 能够获得的最大分数。那么答案就是 。
函数 的计算过程如下：
- 如果 ，说明只剩下一块石子，Alice 无法进行分割，因此返回 。
- 否则，我们枚举分割点 ，即 ，将数组 中下标范围 内的石子分割为 和 两部分，计算出 和 ，分别表示两部分的石子总和。然后我们分别计算 和 ，并更新答案。
注意，如果满足 并且 ，那么这一次枚举可以跳过；如果满足 并且 ，那么后续的枚举都可以跳过，直接退出循环。
最后，我们返回答案即可。
为了避免重复计算，我们可以使用记忆化搜索，同时使用剪枝优化枚举的效率。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
def max(a: int, b: int) -> int:
return a if a > b else b
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= j:
return 0
ans = l = 0
r = s[j + 1] - s[i]
for k in range(i, j):
l += stoneValue[k]
r -= stoneValue[k]
if l < r:
if ans >= l * 2:
continue
ans = max(ans, l + dfs(i, k))
elif l > r:
if ans >= r * 2:
break
ans = max(ans, r + dfs(k + 1, j))
else:
ans = max(ans, max(l + dfs(i, k), r + dfs(k + 1, j)))
return ans
s = list(accumulate(stoneValue, initial=0))
return dfs(0, len(stoneValue) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of dynamic programming and state transitions is key.
- question_mark
Ability to break down the problem into smaller subproblems.
- question_mark
Efficient computation using precomputed sums is a strong signal.
常见陷阱
外企场景- error
Failing to consider all possible divisions of the array.
- error
Not optimizing the solution with precomputed sums, leading to inefficient code.
- error
Overcomplicating the dynamic programming state, missing simpler solutions.
进阶变体
外企场景- arrow_right_alt
Consider variations where Alice's scoring method changes or where Bob's discard rule is different.
- arrow_right_alt
Solve with a greedy strategy or approximate solution to test how close it gets to the optimal solution.
- arrow_right_alt
Explore cases with larger arrays to see how the solution scales.