石子游戏 III 题目描述 Alice 和 Bob 继续他们的石子游戏，这次他们面前有一排石子堆，这些石子堆排成一行，用一个数组 values 表示，其中 values[i] 代表第 i 堆石子的数量。Alice 和 Bob 轮流进行游戏，Alice 先手。在每个玩家的回合中，玩家可以取走这一排石子中最左边的 1堆、2堆、或3堆 石子。游戏持续到所有石子都被取完为止。最终，每个玩家的得分是他们取走的所有石子的总和。我们的目标是判断 Alice 是否能够赢得比赛，假设两位玩家都采取 最优策略 。如果 Alice 的得分大于或等于 Bob 的得分，则 Alice 获胜；否则 Bob 获胜。题目要求返回结果：如果 Alice 获胜，返回 "Alice" ；如果 Bob 获胜，返回 "Bob" ；如果平局，返回 "Tie" 。 解题过程 问题分析 这是一个典型的 博弈类区间动态规划 问题。与之前讲过的“预测赢家”问题不同，这里的操作不是从两端取，而是从 连续的一端（左侧） 取走连续的多堆石子（1堆、2堆或3堆）。这改变了问题的状态定义和转移方式。 关键点在于，由于每次只能从左侧取，游戏的过程实际上是石子堆序列不断 缩短 的过程。状态可以定义为 从某个起始位置到末尾的石子堆序列 。 状态定义 我们定义 dp[i] 表示当石子堆序列为从第 i 堆到最后一堆（即 values[i], values[i+1], ..., values[n-1] ）时， 当前行动的玩家 （无论是 Alice 还是 Bob）能比对手 多获得 的最大分数差值。 n 是石子堆的总数。 如果 dp[0] > 0 ，意味着先手玩家（Alice）能比 Bob 多得分，Alice 获胜。 如果 dp[0] < 0 ，意味着 Bob 能比 Alice 多得分，Bob 获胜。 如果 dp[0] == 0 ，则平局。 状态转移方程 考虑状态 dp[i] ，表示当前剩余石子堆是从第 i 堆开始。 当前玩家有三种选择：取走第 i 堆（1堆），取走第 i 堆和第 i+1 堆（2堆），或者取走第 i , i+1 , i+2 堆（3堆）。 无论当前玩家是谁，他的目标都是 最大化自己相对于对手的分数差 。 假设当前玩家取走了从 i 到 j 的石子堆（ j 可以是 i , i+1 , i+2 ），那么他立即获得的分数是 sum(values[i], values[i+1], ..., values[j]) ，记为 current_take 。 取走之后，剩下的石子堆是从第 j+1 堆开始。此时，轮到对手行动。在状态 dp[j+1] 中，对手会采取最优策略，从而获得相对于当前玩家的分数差为 dp[j+1] 。（注意： dp[j+1] 是从对手视角的分数差）。 那么，在当前玩家取走 current_take 分数后，他相对于对手的分数差就是： current_take - dp[j+1] 。（因为对手的优势 dp[j+1] 是相对于当前玩家的，所以当前玩家要减去这个值才能得到自己的相对优势）。 当前玩家会在三种选择中，选择能使 current_take - dp[j+1] 最大的那个操作。 因此，状态转移方程可以写成： dp[i] = max( current_take_1 - dp[i+1], current_take_2 - dp[i+2], current_take_3 - dp[i+3] ) 其中： current_take_1 = values[i] current_take_2 = values[i] + values[i+1] (需要保证 i+1 < n ) current_take_3 = values[i] + values[i+1] + values[i+2] (需要保证 i+2 < n ) 初始化与边界条件 当 i == n 时，表示没有石子了，当前玩家无石子可拿，相对于对手的分数差为 0。所以 dp[n] = 0 。 对于 i > n 的情况，我们默认 dp[i] = 0 ，表示从越界位置开始，没有石子，分数差为0。 计算顺序 由于状态 dp[i] 依赖于 dp[i+1] , dp[i+2] , dp[i+3] ，即依赖于更靠后的状态，所以我们应该 从后往前 计算 dp 数组。从 i = n-1 开始，一直计算到 i = 0 。 结果判断 计算完 dp[0] 后： 如果 dp[0] > 0 ，返回 "Alice" 。 如果 dp[0] < 0 ，返回 "Bob" 。 如果 dp[0] == 0 ，返回 "Tie" 。 示例演示 假设石子堆为 values = [1, 2, 3, 6] ， n = 4 。 初始化： dp[4] = 0 。 i = 3 ：剩余 [6] 取1堆： 6 - dp[4] = 6 - 0 = 6 取2堆：越界，不考虑。 取3堆：越界，不考虑。 dp[3] = 6 i = 2 ：剩余 [3, 6] 取1堆： 3 - dp[3] = 3 - 6 = -3 取2堆： (3+6) - dp[4] = 9 - 0 = 9 取3堆：越界，不考虑。 dp[2] = max(-3, 9) = 9 i = 1 ：剩余 [2, 3, 6] 取1堆： 2 - dp[2] = 2 - 9 = -7 取2堆： (2+3) - dp[3] = 5 - 6 = -1 取3堆： (2+3+6) - dp[4] = 11 - 0 = 11 dp[1] = max(-7, -1, 11) = 11 i = 0 ：剩余 [1, 2, 3, 6] 取1堆： 1 - dp[1] = 1 - 11 = -10 取2堆： (1+2) - dp[2] = 3 - 9 = -6 取3堆： (1+2+3) - dp[3] = 6 - 6 = 0 dp[0] = max(-10, -6, 0) = 0 结果： dp[0] = 0 ，返回 "Tie" 。 通过这个循序渐进的讲解，你应该能够理解石子游戏 III 的区间动态规划解法了。核心在于状态的定义（当前玩家相对于对手的分数差）和状态转移的逻辑（当前收益减去对手后续的优势）。