石子游戏 VII 题目描述 石子游戏中，一排有 n 堆石子排成一排，每堆石子对应一个价值数组 stones，其中 stones[ i ] 表示第 i 堆石子的价值。两名玩家轮流进行回合，每次回合可以从石排的左端或右端移除一堆石子。游戏终止于所有石子都被移除。 每个玩家的得分为其移除的所有石子的价值之和。每位玩家的目标都是最大化自己的得分差（即自己的得分减去对手的得分）。 假设两位玩家都采用最优策略，请返回先手玩家的得分减去后手玩家的得分的最大值。 解题过程 这是一个典型的区间动态规划问题，我们可以通过以下步骤来解决： 定义状态 设 dp[ i][ j] 表示当石子堆为 stones[ i..j ]（闭区间）时，先手玩家能获得的最大得分差（即先手得分减去后手得分）。 状态转移方程 当轮到当前玩家操作时，他有两种选择： 移除左边的石子堆 stones[ i]，获得价值 stones[ i]，然后面对 stones[ i+1..j ] 移除右边的石子堆 stones[ j]，获得价值 stones[ j]，然后面对 stones[ i..j-1 ] 由于双方都采取最优策略，当前玩家会选择对自己最有利的操作： dp[ i][ j ] = max( stones[ i] - dp[ i+1][ j], // 移除左边，获得stones[ i]，下一轮对手在[ i+1,j ]先手 stones[ j] - dp[ i][ j-1] // 移除右边，获得stones[ j]，下一轮对手在[ i,j-1 ]先手 ) 初始化 当区间长度为1时，即 i = j： dp[ i][ i] = stones[ i ] // 只有一堆石子，先手直接拿走 计算顺序 我们需要按照区间长度从小到大的顺序计算： 先计算所有长度为1的区间 再计算长度为2的区间 然后长度为3的区间 ... 最后计算整个区间 [ 0, n-1 ] 最终结果 返回 dp[ 0][ n-1 ]，即整个石子序列中先手能获得的最大得分差。 举例说明 假设 stones = [ 5, 3, 1, 4, 2 ] 步骤1：初始化长度为1的区间 dp[ 0][ 0 ] = 5 dp[ 1][ 1 ] = 3 dp[ 2][ 2 ] = 1 dp[ 3][ 3 ] = 4 dp[ 4][ 4 ] = 2 步骤2：计算长度为2的区间 dp[ 0][ 1] = max(5 - dp[ 1][ 1], 3 - dp[ 0][ 0 ]) = max(5-3, 3-5) = max(2, -2) = 2 dp[ 1][ 2] = max(3 - dp[ 2][ 2], 1 - dp[ 1][ 1 ]) = max(3-1, 1-3) = max(2, -2) = 2 dp[ 2][ 3] = max(1 - dp[ 3][ 3], 4 - dp[ 2][ 2 ]) = max(1-4, 4-1) = max(-3, 3) = 3 dp[ 3][ 4] = max(4 - dp[ 4][ 4], 2 - dp[ 3][ 3 ]) = max(4-2, 2-4) = max(2, -2) = 2 步骤3：计算长度为3的区间 dp[ 0][ 2] = max(5 - dp[ 1][ 2], 1 - dp[ 0][ 1 ]) = max(5-2, 1-2) = max(3, -1) = 3 dp[ 1][ 3] = max(3 - dp[ 2][ 3], 4 - dp[ 1][ 2 ]) = max(3-3, 4-2) = max(0, 2) = 2 dp[ 2][ 4] = max(1 - dp[ 3][ 4], 2 - dp[ 2][ 3 ]) = max(1-2, 2-3) = max(-1, -1) = -1 步骤4：计算长度为4的区间 dp[ 0][ 3] = max(5 - dp[ 1][ 3], 4 - dp[ 0][ 2 ]) = max(5-2, 4-3) = max(3, 1) = 3 dp[ 1][ 4] = max(3 - dp[ 2][ 4], 2 - dp[ 1][ 3 ]) = max(3-(-1), 2-2) = max(4, 0) = 4 步骤5：计算整个区间 dp[ 0][ 4] = max(5 - dp[ 1][ 4], 2 - dp[ 0][ 3 ]) = max(5-4, 2-3) = max(1, -1) = 1 因此，先手玩家能获得的最大得分差为1。 算法复杂度 时间复杂度：O(n²)，需要计算所有子区间 空间复杂度：O(n²)，用于存储dp表 这个解法通过动态规划完美地模拟了游戏过程，考虑了双方的最优策略选择，确保先手玩家总能做出对自己最有利的决策。