石子游戏问题 题目描述： 有n堆石子排成一行，每堆石子有对应的重量（用数组stones表示）。两个玩家轮流进行游戏，每次玩家可以从当前行的最左端或最右端取走一堆石子，并获得相应的分数（即石子的重量）。游戏结束时得分高者获胜。假设两个玩家都采取最优策略，请你求出先手玩家是否能获胜，或者先手玩家能获得的最大分数差。 解题过程： 这是一个典型的区间动态规划问题，涉及两个玩家的最优策略博弈。我们可以定义状态dp[ i][ j]表示当石子堆为stones[ i...j ]这个子数组时，当前先手玩家能获得的最大分数优势（即先手玩家得分减去后手玩家得分）。 状态转移方程： 当玩家面对石子堆stones[ i...j ]时，有两种选择： 取最左边的石子堆stones[ i]：此时先手玩家获得stones[ i]的分数，然后面对stones[ i+1...j]时，他变成后手玩家。因此，此时先手的优势为：stones[ i] - dp[ i+1][ j ] 取最右边的石子堆stones[ j]：此时先手玩家获得stones[ j]的分数，然后面对stones[ i...j-1]时，他变成后手玩家。因此，此时先手的优势为：stones[ j] - dp[ i][ j-1 ] 取两者中的最大值作为dp[ i][ j ]的值： dp[ i][ j] = max(stones[ i] - dp[ i+1][ j], stones[ j] - dp[ i][ j-1 ]) 边界条件： 当i = j时，即只有一堆石子，先手玩家直接取走，优势为stones[ i ]： dp[ i][ i] = stones[ i ] 计算顺序： 由于dp[ i][ j]依赖于dp[ i+1][ j]和dp[ i][ j-1 ]，我们需要按照区间长度从小到大的顺序计算： 先计算所有长度为1的区间（i = j） 然后计算长度为2的区间 依次增加区间长度，直到计算整个数组dp[ 0][ n-1 ] 最终结果： 如果dp[ 0][ n-1 ] > 0，说明先手玩家能获胜；如果等于0，则为平局；如果小于0，则先手玩家会输。 举例说明： 假设石子堆为[ 3, 2, 10, 4 ]： 长度为1的区间：dp[ 0][ 0]=3, dp[ 1][ 1]=2, dp[ 2][ 2]=10, dp[ 3][ 3 ]=4 长度为2的区间： dp[ 0][ 1] = max(3-dp[ 1][ 1], 2-dp[ 0][ 0 ]) = max(3-2, 2-3) = max(1, -1) = 1 dp[ 1][ 2] = max(2-dp[ 2][ 2], 10-dp[ 1][ 1 ]) = max(2-10, 10-2) = max(-8, 8) = 8 dp[ 2][ 3] = max(10-dp[ 3][ 3], 4-dp[ 2][ 2 ]) = max(10-4, 4-10) = max(6, -6) = 6 长度为3的区间： dp[ 0][ 2] = max(3-dp[ 1][ 2], 10-dp[ 0][ 1 ]) = max(3-8, 10-1) = max(-5, 9) = 9 dp[ 1][ 3] = max(2-dp[ 2][ 3], 4-dp[ 1][ 2 ]) = max(2-6, 4-8) = max(-4, -4) = -4 长度为4的区间： dp[ 0][ 3] = max(3-dp[ 1][ 3], 4-dp[ 0][ 2 ]) = max(3-(-4), 4-9) = max(7, -5) = 7 最终dp[ 0][ 3 ] = 7 > 0，说明先手玩家能获胜，且最大优势为7分。