石子游戏（博弈类区间DP）

题目描述
两个玩家轮流从一排石子的两端取石子。玩家每次可以从当前石子堆的左端或右端取走一整堆石子。每个石子堆有一定的分数（正整数）。游戏结束时，每个玩家获得的分数是他取走的石子堆分数之和。假设两个玩家都采取最优策略，先手玩家能获得的最高分数是多少？
例如：石子堆分数数组为 [3, 9, 1, 2]，先手最优策略下可获最高分数为 11（先取2，后手取3，先手再取9，后手取1）。

解题思路

1. 问题分析

   • 每次操作影响剩余石子堆的区间范围，属于区间DP问题。
   • 关键点：双方均采取最优策略，需用差值法设计状态——记录当前玩家在子区间内能比对手多得的分数。

2. 状态定义

   • 设 dp[i][j] 表示当石子堆为第 i 到第 j 堆时，当前行动玩家比对手多得的分数（含当前回合）。

3. 状态转移

   • 当前玩家有两种选择：
     • 取左端石子堆 piles[i]：对手将在 [i+1, j] 区间内行动，对手多得的分数为 dp[i+1][j]，因此当前玩家多得 piles[i] - dp[i+1][j]。
     • 取右端石子堆 piles[j]：同理，当前玩家多得 piles[j] - dp[i][j-1]。
   • 转移方程：

     dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
     

4. 边界与计算顺序

   • 单堆石子（i == j）：当前玩家直接取走，多得分数为 piles[i]。
   • 按区间长度从小到大计算，确保子区间已求解。

详细步骤
以 piles = [3, 9, 1, 2] 为例：

1. 初始化：单堆区间直接赋值。

   dp[0][0]=3, dp[1][1]=9, dp[2][2]=1, dp[3][3]=2
   

2. 长度=2的区间：
   • [0,1]：max(3-dp[1][1], 9-dp[0][0]) = max(3-9, 9-3) = max(-6, 6) = 6
   • [1,2]：max(9-1, 1-9) = 8
   • [2,3]：max(1-2, 2-1) = 1
3. 长度=3的区间：
   • [0,2]：max(3-dp[1][2], 1-dp[0][1]) = max(3-8, 1-6) = max(-5, -5) = -5
   • [1,3]：max(9-dp[2][3], 2-dp[1][2]) = max(9-1, 2-8) = max(8, -6) = 8
4. 长度=4的区间：
   • [0,3]：max(3-dp[1][3], 2-dp[0][2]) = max(3-8, 2-(-5)) = max(-5, 7) = 7
5. 结果：dp[0][3] = 7 表示先手比后手多7分。总分数为 sum(piles)=15，先手分数 = (15+7)/2 = 11。

总结

• 核心：将“最优策略”转化为最大化当前玩家与对手的分数差。
• 时间复杂度：O(n²)，空间复杂度：O(n²)。
• 扩展：若石子堆成环形，可将数组复制一份转化为线性问题（长度2n）求解。