石子游戏 III

字数 2530 2025-11-06 22:52:24

石子游戏 III

题目描述

Alice 和 Bob 继续他们的石子游戏。现在有一排石子堆，每个石子堆都有一定的价值。玩家轮流从这一排石子堆的左端或右端取走一堆石子。轮到每位玩家时，他们必须取走石子（不能跳过）。游戏持续到所有石子堆都被取完为止。

Alice 先手，Bob 后手。两位玩家都发挥出最佳水平。我们的目标是判断，在游戏结束时，Alice 能够获得的最大石子总价值是多少。假设石子堆的价值数组为 values。

解题过程

这个问题是一个典型的零和博弈问题，可以使用区间动态规划来求解。核心思想是，在一个给定的区间 [i, j] 上，定义 dp[i][j] 为先手玩家在这个区间上能获得的最大分数优势（即先手玩家得分减去后手玩家得分）。

定义状态
设 dp[i][j] 表示当石子堆只剩下从索引 i 到索引 j 的这一段时，当前先手玩家（注意：这个“先手”是相对于当前这个子区间而言的）能比后手玩家多得的石子价值。换句话说，如果当前玩家是 X，对手是 Y，那么 dp[i][j] 表示 X 的得分减去 Y 的得分。
状态转移方程
当轮到当前先手玩家时，他有两种选择：
- 取走最左边的石子堆 (values[i])
  如果他取走了 values[i]，那么剩下的石子堆区间是 [i+1, j]。此时，轮到对手在这个新区间上先手。根据定义，在这个新区间上，对手作为先手，能比当前玩家（现在变成了后手）多得 dp[i+1][j] 分。
  那么，当前玩家在这次选择中，实际获得的分数优势是多少呢？
  他立刻获得了 values[i] 分。之后，在子区间 [i+1, j] 上，对手获得了先手优势 dp[i+1][j]。这意味着，在子游戏结束后，当前玩家的得分将比对手在子游戏中的得分少 dp[i+1][j] 分。
  所以，总的分数优势为：values[i] - dp[i+1][j]。
  （当前获得的 values[i] 减去对手在子游戏中建立的优势）
- 取走最右边的石子堆 (values[j])
  同理，如果他取走了 values[j]，那么剩下的区间是 [i, j-1]。对手在子区间 [i, j-1] 上作为先手，能建立 dp[i][j-1] 的优势。
  所以，当前玩家在这次选择中，总的分数优势为：values[j] - dp[i][j-1]。
作为最佳玩家，他一定会选择能使自己分数优势最大化的那个操作。因此，状态转移方程为：
dp[i][j] = max(values[i] - dp[i+1][j], values[j] - dp[i][j-1])
初始化
考虑区间长度为 1 的情况，即 i == j。
此时，区间里只有一堆石子。当前先手玩家直接取走这堆石子，得分为 values[i]，后手玩家得分为 0。
所以，先手玩家的分数优势就是 values[i] - 0 = values[i]。
因此，dp[i][i] = values[i]。
遍历顺序
由于计算 dp[i][j] 时需要用到 dp[i+1][j]（区间右下方的状态）和 dp[i][j-1]（区间左上方的状态），我们应该从区间长度最短的开始计算，逐步扩大区间长度。
- 外层循环 length 从 1 到 n（石子堆总数）。
- 内层循环 i 从 0 开始，直到 i + length - 1 < n，并令 j = i + length - 1。
得出答案
我们最终要求的是在整个区间 [0, n-1] 上，Alice 作为先手能比 Bob 多多少分，这个值就是 dp[0][n-1]。
那么，Alice 的实际得分是多少呢？
设总石子价值为 total = sum(values)。
游戏结果是零和的：Alice 得分 + Bob 得分 = total。
同时，根据 dp[0][n-1] 的定义：Alice 得分 - Bob 得分 = dp[0][n-1]。
解这个二元一次方程组：
- Alice 得分 = (total + dp[0][n-1]) / 2
  因为题目通常只要求判断 Alice 是否能赢，或者直接要求 Alice 的最大得分，所以 (total + dp[0][n-1]) / 2 就是最终的答案。如果只问输赢，可以看 dp[0][n-1] 是否大于 0。

举例说明

假设石子堆价值数组为 values = [1, 2, 3]。

初始化 (length = 1)：
dp[0][0] = 1
dp[1][1] = 2
dp[2][2] = 3
计算长度为 2 的区间 (length = 2)：
- 区间 [0, 1]：dp[0][1] = max(values[0] - dp[1][1], values[1] - dp[0][0]) = max(1-2, 2-1) = max(-1, 1) = 1
- 区间 [1, 2]：dp[1][2] = max(values[1] - dp[2][2], values[2] - dp[1][1]) = max(2-3, 3-2) = max(-1, 1) = 1
计算长度为 3 的区间 (length = 3)：
- 区间 [0, 2]：dp[0][2] = max(values[0] - dp[1][2], values[2] - dp[0][1]) = max(1-1, 3-1) = max(0, 2) = 2
得出答案：
总价值 total = 1+2+3 = 6。
Alice 得分 = (total + dp[0][2]) / 2 = (6 + 2) / 2 = 4。
所以，Alice 最多能获得 4 分。（实际策略：Alice 先拿 3（右边），然后 Bob 无论拿 1 还是 2，Alice 都可以拿剩下的那个，最终 Alice 得 3+1=4 分）。

石子游戏 III 题目描述 Alice 和 Bob 继续他们的石子游戏。现在有一排石子堆，每个石子堆都有一定的价值。玩家轮流从这一排石子堆的左端或右端取走一堆石子。轮到每位玩家时，他们必须取走石子（不能跳过）。游戏持续到所有石子堆都被取完为止。 Alice 先手，Bob 后手。两位玩家都发挥出最佳水平。我们的目标是判断，在游戏结束时，Alice 能够获得的最大石子总价值是多少。假设石子堆的价值数组为 values 。解题过程这个问题是一个典型的零和博弈问题，可以使用区间动态规划来求解。核心思想是，在一个给定的区间 [i, j] 上，定义 dp[i][j] 为先手玩家在这个区间上能获得的最大分数优势（即先手玩家得分减去后手玩家得分）。定义状态设 dp[i][j] 表示当石子堆只剩下从索引 i 到索引 j 的这一段时，当前先手玩家（注意：这个“先手”是相对于当前这个子区间而言的）能比后手玩家多得的石子价值。换句话说，如果当前玩家是 X，对手是 Y，那么 dp[i][j] 表示 X 的得分减去 Y 的得分。状态转移方程当轮到当前先手玩家时，他有两种选择：取走最左边的石子堆 ( values[i] ) 如果他取走了 values[i] ，那么剩下的石子堆区间是 [i+1, j] 。此时，轮到对手在这个新区间上先手。根据定义，在这个新区间上，对手作为先手，能比当前玩家（现在变成了后手）多得 dp[i+1][j] 分。那么，当前玩家在这次选择中，实际获得的分数优势是多少呢？他立刻获得了 values[i] 分。之后，在子区间 [i+1, j] 上，对手获得了先手优势 dp[i+1][j] 。这意味着，在子游戏结束后，当前玩家的得分将比对手在子游戏中的得分少 dp[i+1][j] 分。所以，总的分数优势为： values[i] - dp[i+1][j] 。（当前获得的 values[i] 减去对手在子游戏中建立的优势）取走最右边的石子堆 ( values[j] ) 同理，如果他取走了 values[j] ，那么剩下的区间是 [i, j-1] 。对手在子区间 [i, j-1] 上作为先手，能建立 dp[i][j-1] 的优势。所以，当前玩家在这次选择中，总的分数优势为： values[j] - dp[i][j-1] 。作为最佳玩家，他一定会选择能使自己分数优势最大化的那个操作。因此，状态转移方程为： dp[i][j] = max(values[i] - dp[i+1][j], values[j] - dp[i][j-1]) 初始化考虑区间长度为 1 的情况，即 i == j 。此时，区间里只有一堆石子。当前先手玩家直接取走这堆石子，得分为 values[i] ，后手玩家得分为 0。所以，先手玩家的分数优势就是 values[i] - 0 = values[i] 。因此， dp[i][i] = values[i] 。遍历顺序由于计算 dp[i][j] 时需要用到 dp[i+1][j] （区间右下方的状态）和 dp[i][j-1] （区间左上方的状态），我们应该从区间长度最短的开始计算，逐步扩大区间长度。外层循环 length 从 1 到 n （石子堆总数）。内层循环 i 从 0 开始，直到 i + length - 1 < n ，并令 j = i + length - 1 。得出答案我们最终要求的是在整个区间 [0, n-1] 上，Alice 作为先手能比 Bob 多多少分，这个值就是 dp[0][n-1] 。那么，Alice 的实际得分是多少呢？设总石子价值为 total = sum(values) 。游戏结果是零和的：Alice 得分 + Bob 得分 = total。同时，根据 dp[0][n-1] 的定义：Alice 得分 - Bob 得分 = dp[0][n-1] 。解这个二元一次方程组： Alice 得分 = ( total + dp[0][n-1] ) / 2 因为题目通常只要求判断 Alice 是否能赢，或者直接要求 Alice 的最大得分，所以 (total + dp[0][n-1]) / 2 就是最终的答案。如果只问输赢，可以看 dp[0][n-1] 是否大于 0。举例说明假设石子堆价值数组为 values = [1, 2, 3] 。初始化 ( length = 1 )： dp[0][0] = 1 dp[1][1] = 2 dp[2][2] = 3 计算长度为 2 的区间 ( length = 2 )：区间 [0, 1] ： dp[0][1] = max(values[0] - dp[1][1], values[1] - dp[0][0]) = max(1-2, 2-1) = max(-1, 1) = 1 区间 [1, 2] ： dp[1][2] = max(values[1] - dp[2][2], values[2] - dp[1][1]) = max(2-3, 3-2) = max(-1, 1) = 1 计算长度为 3 的区间 ( length = 3 )：区间 [0, 2] ： dp[0][2] = max(values[0] - dp[1][2], values[2] - dp[0][1]) = max(1-1, 3-1) = max(0, 2) = 2 得出答案：总价值 total = 1+2+3 = 6 。 Alice 得分 = ( total + dp[0][2] ) / 2 = (6 + 2) / 2 = 4。所以，Alice 最多能获得 4 分。（实际策略：Alice 先拿 3（右边），然后 Bob 无论拿 1 还是 2，Alice 都可以拿剩下的那个，最终 Alice 得 3+1=4 分）。