环形石子游戏（博弈类区间DP） 题目描述 有 n 堆石子排成一个环形，每堆石子有一定数量，用一个整数数组 stones 表示，其中 stones[ i ] 表示第 i 堆石子的数量。Alice 和 Bob 轮流进行游戏，由 Alice 先手。每一回合，玩家可以从环中任选一堆石子（第一次除外，第一次必须从某堆开始），但必须满足以下条件： 如果这是该玩家的第一次操作，他可以选择任意一堆石子（由于是环形，任意一堆均可作为起点）。 如果不是第一次操作，则选择的石子堆必须与上一回合（无论是自己还是对手）选择的石子堆在环上相邻（即索引 i 与 i-1 或 i+1 相邻，考虑环形后模 n 处理）。 当一名玩家无法进行合法操作时（即所有石子堆都已为空），游戏结束。每个玩家的得分是他所取石子数量之和。两名玩家都采取最优策略，目标是最大化自己的得分。请问，如果 Alice 和 Bob 都发挥最佳，Alice 最终能比 Bob 多多少分？假设总石子数量为 S，则 Alice 的得分减去 Bob 的得分即为结果。 示例 输入：stones = [ 1, 2, 3, 4 ] 输出：2 解释：Alice 先手，她可以选择任意一堆。最优策略是： Alice 取 stones[ 3 ] = 4（索引从0开始），得分 4。 现在环上剩下 [ 1, 2, 3]，Bob 必须选择与索引 3 相邻的堆（即索引 0 或 2），假设 Bob 取 stones[ 2 ] = 3，得分 3。 剩下 [ 1, 2]，Alice 取 stones[ 1 ] = 2，得分 2（累计 6）。 Bob 只能取 stones[ 0 ] = 1，得分 1（累计 4）。 Alice 比 Bob 多 6 - 4 = 2 分。 解题过程（循序渐进） 步骤1：理解问题并转化 这是一个环形博弈问题，关键点在于： 环形结构：n 堆石子，索引 0 和 n-1 相邻。 操作规则：第一次任意选，后续必须选与上次操作（任意玩家）相邻的堆。 石子被取走后，该堆变为空，后续不能再选。 游戏结束时所有堆为空，总得分固定为 S（总石子数）。若 Alice 得分为 A，Bob 为 B，则 A + B = S，问题求 A - B = 2A - S。 因此，只需计算 Alice 能获得的最大得分 A，则结果 = 2A - S。 步骤2：分析操作对环的影响 由于操作必须相邻，实际上每次选择后，环会被“切断”： 第一次选择任意堆 i，该堆被取走，环被断开为一条链（从 i+1 到 i-1，模 n 处理）。 后续每次选择，玩家只能在当前链的两端选取（因为只有两端与已取走的空堆相邻）。 这样，问题转化为：在一条链上，玩家轮流从两端取石子，求先手能获得的最大石子数。但第一次是任意选堆，因此需要枚举第一次的选择。 步骤3：子问题定义（链上博弈） 假设当前链为 stones[ l..r]（闭区间），先手玩家能获得的最大石子数记为 dp[ l][ r ]（区间动态规划）。 若 l > r，区间为空，dp[ l][ r ] = 0。 当前先手可以选择取左端 stones[ l] 或右端 stones[ r ]： 取左端：先手获得 stones[ l]，剩余区间 [ l+1, r] 由后手先取。后手也会最优，因此后手能获得 dp[ l+1][ r]，则先手实际获得 stones[ l] + (sum(l+1, r) - dp[ l+1][ r ])，其中 sum(l+1, r) 是区间总和。 取右端：类似，先手获得 stones[ r] + (sum(l, r-1) - dp[ l][ r-1 ])。 先手取最大值： dp[ l][ r] = max(stones[ l] + sum(l+1, r) - dp[ l+1][ r ], stones[ r] + sum(l, r-1) - dp[ l][ r-1 ])。 注意到 sum(l+1, r) = total(l, r) - stones[ l]，其中 total(l, r) 是区间 [ l, r ] 总和。因此可化简： dp[ l][ r] = total(l, r) - min(dp[ l+1][ r], dp[ l][ r-1 ])。 步骤4：处理环形 第一次 Alice 可以选择任意堆 i，取走 stones[ i]，环断开为链 stones[ i+1..i-1 ]（模 n）。之后 Bob 作为新链的先手。 因此，若 Alice 第一次取 stones[ i ]，她后续能获得的石子数 = 剩余链上 Bob 作为先手时，Bob 能获得的最大值？不，Alice 是后手。 准确说：第一次后，剩余链 stones[ i+1..i-1]（模 n），Bob 先手，Alice 后手。Bob 在剩余链上能获得 dp[ i+1][ i-1]（模 n 索引），则 Alice 在剩余链上获得 sum_ remain - dp[ i+1][ i-1]，其中 sum_ remain 是剩余链的总和 = S - stones[ i ]。 因此 Alice 总得分 = stones[ i] + (S - stones[ i] - dp[ i+1][ i-1]) = S - dp[ i+1][ i-1 ]。 我们需要最大化 Alice 总得分，即枚举 i，求 min(dp[ i+1][ i-1])（因为 A = S - dp[ i+1][ i-1]，最小化 dp[ i+1][ i-1 ]）。 步骤5：环形索引处理与DP计算 将原数组复制一倍：stones2 = stones + stones，长度 2n。 在 stones2 上定义区间 dp[ l][ r]（0 ≤ l ≤ r < 2n），表示在链 stones2[ l..r ] 上先手能获得的最大石子数。 转移方程： dp[ l][ r] = total(l, r) - min(dp[ l+1][ r], dp[ l][ r-1 ])，其中 total(l, r) 用前缀和快速计算。 初始化：dp[ i][ i] = stones2[ i ]（区间长度为1时，先手只能取该堆）。 计算顺序：区间长度 len 从 2 到 n（注意我们只需要长度 ≤ n 的区间，因为剩余链长度最多 n-1）。 步骤6：枚举第一次选择并求答案 对于每个 i (0 ≤ i < n)，剩余链在 stones2 上的区间为 [ i+1, i-1+n ]（因为复制后，i+1 到 i-1+n 是环形上 i 之后到 i 之前的链，长度 n-1）。 则 dp[ i+1][ i-1+n ] 表示 Bob 在剩余链上作为先手的最大得分。 Alice 总得分 A_ i = S - dp[ i+1][ i-1+n ]。 取最大值 A = max(A_ i)。 最终答案 = 2A - S。 步骤7：示例演算（stones = [ 1,2,3,4]） S = 10。 复制数组：stones2 = [ 1,2,3,4,1,2,3,4 ]。 计算 dp 表（关键值）： dp[ 1][ 4]（剩余链对应 i=0 选择后，Bob 先手链 [ 2,3,4,1 ]）： len=4，计算得 dp[ 1][ 4] = 10 - min(dp[ 2][ 4], dp[ 1][ 3 ]) = 10 - min(7, 6) = 10 - 6 = 4。 因此 A_ 0 = 10 - 4 = 6。 类似计算其他 i，发现 A 最大为 6（i=0 或 i=3 时）。 答案 = 2* 6 - 10 = 2。 步骤8：复杂度 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n) 但实现较复杂）。本题 n 一般 ≤ 500，O(n²) 可行。 这样，我们就通过区间动态规划解决了环形石子游戏问题。