石子游戏 VIII 题目描述 Alice 和 Bob 正在玩一个石子游戏。有 n 堆石子排成一行，每堆石子有一个正整数数值 piles[ i ]。游戏规则如下： Alice 先手，Bob 后手。 每一轮，当前玩家可以从剩下的石子堆的 最左端 或者 最右端 取走一堆石子。 游戏持续到所有石子堆都被取完。 玩家的最终得分是他取走的所有石子堆的数值之和。 但在这个版本（VIII）中，目标不是最大化自己的绝对得分，而是 最大化自己与对手的得分差 。 假设 Alice 和 Bob 都发挥出最佳水平，请返回 Alice 能取得的对 Bob 的最大得分差。 解题过程 问题分析与状态定义 这是一个典型的零和博弈问题，适合用区间动态规划求解。我们定义 dp[i][j] 为当石子堆只剩下从第 i 堆到第 j 堆（闭区间 [ i, j ]）时，当前行动玩家（无论是谁）能获得的最大得分差。 这个得分差是从当前玩家的视角：如果当前玩家在这段区间上行动，他最终能比对手多多少分。 状态转移方程 当区间 [ i, j ] 只剩下一个玩家行动时： 如果当前玩家取走 piles[ i]，那么他立即获得 piles[ i] 的分数，然后轮到对手在区间 [ i+1, j] 上行动。根据定义，对手在 [ 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]) 初始化 当区间长度为 1（即 i == j）时，只有一堆石子，当前玩家直接取走，得分差就是 piles[ i ]： dp[i][i] = piles[i] 计算顺序 由于区间动态规划通常按照区间长度从小到大计算： 先计算所有长度为 1 的区间 然后计算长度为 2 的区间 接着计算长度为 3 的区间 ... 最后计算长度为 n 的区间 [ 0, n-1 ] 最终结果 游戏开始时，石子堆是完整的区间 [ 0, n-1]，且 Alice 是先手玩家，所以最终结果是 dp[0][n-1] 。 举例说明 假设 piles = [ 3, 9, 1, 2 ] 按照区间长度从小到大计算： 长度 1：dp[ 0][ 0]=3, dp[ 1][ 1]=9, dp[ 2][ 2]=1, dp[ 3][ 3 ]=2 长度 2： dp[ 0][ 1] = max(3-dp[ 1][ 1], 9-dp[ 0][ 0 ]) = max(3-9, 9-3) = max(-6, 6) = 6 dp[ 1][ 2] = max(9-dp[ 2][ 2], 1-dp[ 1][ 1 ]) = max(9-1, 1-9) = max(8, -8) = 8 dp[ 2][ 3] = max(1-dp[ 3][ 3], 2-dp[ 2][ 2 ]) = max(1-2, 2-1) = max(-1, 1) = 1 长度 3： dp[ 0][ 2] = max(3-dp[ 1][ 2], 1-dp[ 0][ 1 ]) = max(3-8, 1-6) = max(-5, -5) = -5 dp[ 1][ 3] = max(9-dp[ 2][ 3], 2-dp[ 1][ 2 ]) = max(9-1, 2-8) = max(8, -6) = 8 长度 4： dp[ 0][ 3] = max(3-dp[ 1][ 3], 2-dp[ 0][ 2 ]) = max(3-8, 2-(-5)) = max(-5, 7) = 7 最终结果 dp[ 0][ 3 ] = 7，表示 Alice 能取得对 Bob 的最大得分差为 7。