石子游戏 II 题目描述 给定一个整数数组 piles ，表示一排石子的数量。两名玩家轮流从石堆的 最左端 或 最右端 取石子，每次必须取走至少一堆（即取走最左或最右的一整堆石子）。游戏的目标是拿到最多的石子。假设两名玩家都采取最优策略，先手玩家能获得的最大石子总数是多少？ 示例 输入： piles = [5, 3, 4, 5] 输出：先手能获得的最大石子数为 10 （解释：先手取右端5，后手取左端5，先手再取4，后手取3，先手总数为5+4=9？需重新计算，实际最优解应为10，具体步骤见下文分析）。 解题思路 问题分析 每次只能从两端取石子，且必须取一整堆，这属于 两端取物的博弈问题 。 关键点：当前玩家选择左端或右端后，剩余石子堆构成一个子区间，后手玩家会在子区间上继续最优决策。 状态定义 设 dp[i][j] 表示当石子堆为区间 [i, j] 时， 当前先手玩家 能比后手玩家多拿的石子数（注意：不是绝对石子数，而是差值）。 最终答案：先手比后手多拿的差值 diff = dp[0][n-1] ，先手实际石子数 = (总石子数 + diff) / 2 。 状态转移 若当前玩家取左端 piles[i] ，则后手在 [i+1, j] 上先手，差值 = piles[i] - dp[i+1][j] （因为后手变先手后，其差值优势是 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]) 。 边界条件 当 i == j 时，只有一堆石子，全被当前玩家拿走， dp[i][i] = piles[i] 。 计算顺序 区间DP需按区间长度从小到大计算：先算长度为1的区间，再算长度为2的区间，直到整个区间 [0, n-1] 。 详细计算步骤（以示例 [ 5, 3, 4, 5] 为例） 初始化： n = 4 ，总石子数 = 5+3+4+5=17。 长度为1的区间： dp[0][0]=5 , dp[1][1]=3 , dp[2][2]=4 , dp[3][3]=5 。 长度为2的区间： [0,1] ：取左5-3=2，取右3-5=-2，选最大2 → dp[0][1]=2 。 [1,2] ：取左3-4=-1，取右4-3=1，选最大1 → dp[1][2]=1 。 [2,3] ：取左4-5=-1，取右5-4=1，选最大1 → dp[2][3]=1 。 长度为3的区间： [0,2] ：取左5 - dp[ 1][ 2]=5-1=4，取右4 - dp[ 0][ 1]=4-2=2，选最大4 → dp[0][2]=4 。 [1,3] ：取左3 - dp[ 2][ 3]=3-1=2，取右5 - dp[ 1][ 2]=5-1=4，选最大4 → dp[1][3]=4 。 整个区间 [0,3] ： 取左5 - dp[ 1][ 3]=5-4=1，取右5 - dp[ 0][ 2]=5-4=1，两者相同 → dp[0][3]=1 。 先手得分 = (总石子17 + 差值1) / 2 = 9 ？但示例输出为10，说明需检查。 发现错误 ：示例中实际最优解是先手取左5，后手取左3，先手再取右5，后手取4，先手总5+5=10。 问题出在 状态定义 ：应直接定义 dp[i][j] 为区间 [i, j] 上先手能拿的 最大石子数 ，而不是差值。 修正后的状态定义与转移 状态定义 ： dp[i][j] 表示在区间 [i, j] 上，先手玩家能获得的最大石子数。 转移方程 ： 若先手取左端 piles[i] ，则后手在 [i+1, j] 上先手，先手获得 = piles[i] + (区间[i+1, j]的总和 - dp[i+1][j]) （因为后手拿走后，剩余归先手）。 简化：设 sum[i][j] 为区间和，则先手取左端时得分 = piles[i] + sum[i+1][j] - dp[i+1][j] 。 同理，取右端得分 = piles[j] + sum[i][j-1] - dp[i][j-1] 。 因此 dp[i][j] = max(piles[i] + sum[i+1][j] - dp[i+1][j], piles[j] + sum[i][j-1] - dp[i][j-1]) 。 可预处理前缀和快速求区间和。 重新计算示例 [ 5, 3, 4, 5] 区间和： sum[0][3]=17 。 长度1： dp[0][0]=5 , dp[1][1]=3 , dp[2][2]=4 , dp[3][3]=5 。 长度2： [0,1] ：取左5+(3-3)=5，取右3+(5-5)=3，选5 → dp[0][1]=5 。 [1,2] ：取左3+(4-4)=3，取右4+(3-3)=4，选4 → dp[1][2]=4 。 [2,3] ：取左4+(5-5)=4，取右5+(4-4)=5，选5 → dp[2][3]=5 。 长度3： [0,2] ：取左5+(3+4-4)=8，取右4+(5+3-5)=7，选8 → dp[0][2]=8 。 [1,3] ：取左3+(4+5-5)=7，取右5+(3+4-4)=8，选8 → dp[1][3]=8 。 长度4 [0,3] ： 取左5+(3+4+5-8)=9，取右5+(5+3+4-8)=9，两者均为9？但实际最优解为10，说明仍有问题。 关键修正 ：取左端时，剩余区间 [i+1, j] 的总和是 sum[i+1][j] ，但后手在 [i+1, j] 上作为先手拿的是 dp[i+1][j] ，剩余部分 sum[i+1][j] - dp[i+1][j] 归当前先手。 但此处理正确，为何结果不符？因实际最优路径是：先手取左5 → 剩[ 3,4,5]，后手取左3 → 剩[ 4,5]，先手取右5 → 剩[ 4 ]，后手取4。先手总5+5=10。 计算 dp[0][3] ：取左5+sum[ 1][ 3]-dp[ 1][ 3]=5+12-8=9；取右5+sum[ 0][ 2]-dp[ 0][ 2 ]=5+12-8=9。 矛盾原因：当先手取左5后，后手在[ 1,3]上应取最优（取右5得8），而非取左3。但后手取右5时，先手在[ 1,2 ]上能拿4，后手拿3，先手总5+4=9。 因此正确答案是9，示例输出10有误。 结论 正确解法： dp[i][j] = max(sum[i][j] - dp[i+1][j], sum[i][j] - dp[i][j-1]) ，其中 sum[i][j] 可前缀和优化。 最终 dp[0][n-1] 即先手最大石子数。 本问题实为 石子游戏 的标准区间DP解法，注意与预测赢家区别（预测赢家是取数而非取整堆）。