石子游戏 III
题目描述
Alice 和 Bob 继续他们的石子游戏。现在有一排石子堆，这些石子堆排成一行，每堆石子都有对应的价值。我们用数组 stoneValue 表示这些石子堆的价值，数组长度记为 n。
Alice 和 Bob 轮流进行游戏，Alice 先手。在每个玩家的回合中，玩家可以从这一排石子堆的剩余部分的起始位置（即当前最左边的石子堆）开始，拿走 1 堆、2 堆 或 3 堆 石子。
游戏一直进行，直到没有更多的石子堆为止。
每个玩家的得分是他们拿到的所有石子堆的价值总和。每个玩家的目标都是最大化自己的得分，并且双方都采取最优策略。
最终，得分高的玩家获胜。如果两位玩家得分相同，则游戏平局。
假设 Alice 和 Bob 都足够聪明，请判断 Alice 是赢、输还是平局。如果 Alice 获胜，返回 "Alice"；如果 Bob 获胜，返回 "Bob"；如果平局，返回 "Tie"。
解题过程
-
问题分析与状态定义
这是一个典型的零和博弈问题，可以使用区间动态规划（DP）来解决。关键在于，在每一步，当前玩家都面临一个“子数组”（即从索引i到数组末尾的石子堆），并需要做出最优决策。
我们定义状态dp[i]：表示当剩余的石子堆是子数组stoneValue[i:]（即从第i堆到最后一堆）时，当前行动的玩家（不一定是 Alice）可以比对手多得的分数。- 注意是“当前行动的玩家”比对手多得的分数。如果当前玩家是 Alice，那么
dp[0]就表示 Alice 能比 Bob 多得的分数。 - 如果
dp[i] > 0，意味着面对剩余石子堆stoneValue[i:]，当前行动的玩家可以获胜。 - 如果
dp[i] < 0，意味着当前行动的玩家会落后（即对手会获胜）。 - 如果
dp[i] = 0，意味着会平局。
- 注意是“当前行动的玩家”比对手多得的分数。如果当前玩家是 Alice，那么
-
状态转移方程
当轮到某个玩家行动时，他面对的是从索引i开始的石子堆。他可以选择拿走最左边的 1 堆、2 堆或 3 堆石子。- 如果他拿走 1 堆（即拿走
stoneValue[i]），那么他立即获得stoneValue[i]的分数。接下来，轮到对手在从索引i+1开始的石子堆上行动。根据dp[i+1]的定义，它表示对手（作为新的当前行动者）在剩余石子堆上能比“他的对手”（也就是原来的当前玩家）多得的分数。因此，对于原来的当前玩家来说，他在这步操作后，最终能比对手多得的分数是：(他得到的分数) - (对手比他多得的分数)=stoneValue[i] - dp[i+1]。 - 类似地，如果他拿走 2 堆（即拿走
stoneValue[i] + stoneValue[i+1]），那么他最终能比对手多得的分数是：(stoneValue[i] + stoneValue[i+1]) - dp[i+2]。 - 如果他拿走 3 堆（即拿走
stoneValue[i] + stoneValue[i+1] + stoneValue[i+2]），那么他最终能比对手多得的分数是：(stoneValue[i] + stoneValue[i+1] + stoneValue[i+2]) - dp[i+3]。
由于当前玩家采取最优策略，他会选择能使自己相对得分（即比对手多得的分数）最大化的那种拿法。
因此，状态转移方程为：
dp[i] = max( option1, option2, option3 )
其中：
option1 = stoneValue[i] - dp[i+1]
option2 = stoneValue[i] + stoneValue[i+1] - dp[i+2](需确保i+1 < n)
option3 = stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - dp[i+3](需确保i+2 < n) - 如果他拿走 1 堆（即拿走
-
初始化与计算顺序
- 边界情况：当
i == n时，表示没有石子堆了。当前玩家无石子可拿，得到的分数为 0，对手的分数也是 0（因为游戏结束），所以当前玩家比对手多得的分数为 0。因此，dp[n] = 0。 - 计算顺序：由于状态
dp[i]依赖于dp[i+1]，dp[i+2]，dp[i+3]这些更大的索引对应的状态，所以我们需要从后往前计算dp数组。即从i = n-1开始，递减到i = 0。
- 边界情况：当
-
结果判断
计算完dp数组后，我们看dp[0]的值，它表示 Alice（作为先手玩家）在完整的石子堆序列上，能比 Bob 多得的分数。- 如果
dp[0] > 0，则 Alice 获胜，返回 "Alice"。 - 如果
dp[0] < 0，则 Bob 获胜，返回 "Bob"。 - 如果
dp[0] == 0，则平局，返回 "Tie"。
- 如果
-
示例说明
假设石子堆价值数组为stoneValue = [1, 2, 3, 7]。n = 4。初始化dp[4] = 0。- 计算
i = 3（剩余[7]）：- 拿 1 堆：
7 - dp[4] = 7 - 0 = 7 - 只能拿 1 堆。
dp[3] = 7
- 拿 1 堆：
- 计算
i = 2（剩余[3, 7]）：- 拿 1 堆：
3 - dp[3] = 3 - 7 = -4 - 拿 2 堆：
(3+7) - dp[4] = 10 - 0 = 10 dp[2] = max(-4, 10) = 10
- 拿 1 堆：
- 计算
i = 1（剩余[2, 3, 7]）：- 拿 1 堆：
2 - dp[2] = 2 - 10 = -8 - 拿 2 堆：
(2+3) - dp[3] = 5 - 7 = -2 - 拿 3 堆：
(2+3+7) - dp[4] = 12 - 0 = 12 dp[1] = max(-8, -2, 12) = 12
- 拿 1 堆：
- 计算
i = 0（剩余[1, 2, 3, 7]）：- 拿 1 堆：
1 - dp[1] = 1 - 12 = -11 - 拿 2 堆：
(1+2) - dp[2] = 3 - 10 = -7 - 拿 3 堆：
(1+2+3) - dp[3] = 6 - 7 = -1 dp[0] = max(-11, -7, -1) = -1
- 拿 1 堆：
- 因为
dp[0] = -1 < 0，所以 Bob 获胜，返回 "Bob"。
总结
这个问题的核心在于定义状态 dp[i] 为当前玩家在子数组 stoneValue[i:] 上能获得的最大相对优势（比对手多得的分数）。通过从后往前动态规划，并考虑每一步的三种选择，我们可以计算出最终先手玩家 Alice 的相对优势 dp[0]，从而判断游戏结果。