石子游戏 VI（Alice 和 Bob 的博弈，石子价值与移除成本） 题目描述 给定一个整数数组 stones ， stones[i] 表示第 `i `` 堆石子的价值。Alice 和 Bob 轮流进行游戏，Alice 先手。在每一回合中，玩家可以从数组的 最左端 或 最右端 移除一堆石子，并获得相应的分数，但移除操作本身会有一个 成本 ，成本等于 被移除石子时，数组中剩余石子的总价值之和 。玩家的最终得分是获得的分数减去所有移除操作的成本总和。游戏结束时所有石子被移除。假设 Alice 和 Bob 都采用最优策略，都希望最大化自己的 净得分 （得分减去成本），返回 Alice 能否获胜（即净得分是否大于 Bob）。如果净得分相同，则视为 Alice 失败（返回 false）。 示例 输入： stones = [5, 3, 1, 4, 2] 解释：总价值为 5+3+1+4+2 = 15。 如果 Alice 先取最左的 5，她得到分数 5，移除成本 = 剩余石子总价值 15-5=10，净得分 = 5-10 = -5。剩余 [ 3,1,4,2 ]。 Bob 面对 [ 3,1,4,2 ] 总价值 10，若取最左 3，得分 3，成本 = 10-3=7，净得分 = 3-7 = -4，但 Bob 会选择最优。 需用动态规划判断最终结果。 解题思路 定义问题 设数组长度为 n，总价值 sum = sum(stones[ 0..n-1 ])。 当从一端取走 stones[ i] 时，当前剩余石子总价值为 current_ sum，则： 玩家得分增加 stones[ i]，成本为 (current_ sum - stones[ i])，因此 净收益 = stones[ i] - (current_ sum - stones[ i]) = 2* stones[ i] - current_ sum。 注意：current_ sum 是取之前的剩余总和。 状态设计 用 dp[ l][ r] 表示当石子剩下区间 [ l, r] 时，当前行动玩家（可能是 Alice 或 Bob）能取得的 最大净收益 （即当前玩家在剩余区间内能获得的“自己得分减去对手得分”的最大差值，这里的收益是指净收益，已经包含了成本计算后的结果）。 那么最终如果 dp[ 0][ n-1 ] > 0，Alice 净收益大于 Bob，获胜。 状态转移 在区间 [ l, r]，当前剩余总和 S = prefix[ r+1] - prefix[ l ]（用前缀和快速计算）。 如果取左端 stones[ l ]： 取走 stones[ l] 后，新剩余总和为 S - stones[ l]，当前玩家净收益 = (2 stones[ l] - S) + ( - dp[ l+1][ r ] )？这里需要注意逻辑。 实际上，我们定义 dp[ l][ r] 为当前玩家在区间 [ l,r ] 内可获得的“与对手的净收益差值”。 设当前玩家取左端，他立即获得的净收益为 2 stones[ l] - S，之后轮到对手在 [ l+1,r] 区间行动，对手在该区间可获得的“与当前玩家的净收益差值”是 dp[ l+1][ r ]（对手视角）。 那么在当前玩家视角，对手获得的净收益会从当前玩家的净收益中扣除，因此当前玩家最终净收益差值 = (2 stones[ l] - S) - dp[ l+1][ r ]。 同理，取右端 stones[ r]：净收益差值 = (2 stones[ r] - S) - dp[ l][ r-1 ]。 当前玩家选择两者较大值。 初始化 当 l == r 时，剩余总和 S = stones[ l]，取走它，净收益差值 = 2* stones[ l] - stones[ l] = stones[ l ]（因为成本为0）。 所以 dp[ l][ l] = stones[ l ]。 计算顺序 区间 DP 典型顺序：按区间长度 len 从 1 到 n 递增计算。 结果判断 dp[ 0][ n-1 ] > 0 则 Alice 胜，否则败。 逐步演算 （示例 stones = [ 5,3,1,4,2 ]，n=5） 总价值 sum=15。 prefix=[ 0,5,8,9,13,15 ]。 len=1: dp[ 0][ 0]=5, dp[ 1][ 1]=3, dp[ 2][ 2]=1, dp[ 3][ 3]=4, dp[ 4][ 4 ]=2。 len=2: 计算 [ 0,1]：S=prefix[ 2]-prefix[ 0 ]=8。 取左：收益=2 5-8=2, 减去dp[ 1][ 1 ]=3 → 2-3=-1。 取右：收益=2 3-8=-2, 减去dp[ 0][ 0 ]=5 → -2-5=-7。 max(-1,-7)=-1，dp[ 0][ 1 ]=-1。 同理 [ 1,2]：S=prefix[ 3]-prefix[ 1 ]=9-5=4。 取左：2 3-4=2, 减dp[ 2][ 2 ]=1 → 2-1=1。 取右：2 1-4=-2, 减dp[ 1][ 1 ]=3 → -2-3=-5。 max=1 → dp[ 1][ 2 ]=1。 [ 2,3]：S=prefix[ 4]-prefix[ 2 ]=13-8=5。 取左：2 1-5=-3, 减dp[ 3][ 3 ]=4 → -3-4=-7。 取右：2 4-5=3, 减dp[ 2][ 2 ]=1 → 3-1=2。 max=2 → dp[ 2][ 3 ]=2。 [ 3,4]：S=prefix[ 5]-prefix[ 3 ]=15-9=6。 取左：2 4-6=2, 减dp[ 4][ 4 ]=2 → 2-2=0。 取右：2 2-6=-2, 减dp[ 3][ 3 ]=4 → -2-4=-6。 max=0 → dp[ 3][ 4 ]=0。 len=3: [ 0,2]：S=prefix[ 3]-prefix[ 0 ]=9。 取左：2 5-9=1, 减dp[ 1][ 2 ]=1 → 0。 取右：2 1-9=-7, 减dp[ 0][ 1 ]=-1 → -7-(-1)=-6。 max=0 → dp[ 0][ 2 ]=0。 [ 1,3]：S=prefix[ 4]-prefix[ 1 ]=13-5=8。 取左：2 3-8=-2, 减dp[ 2][ 3 ]=2 → -4。 取右：2 4-8=0, 减dp[ 1][ 2 ]=1 → -1。 max=-1 → dp[ 1][ 3 ]=-1。 [ 2,4]：S=prefix[ 5]-prefix[ 2 ]=15-8=7。 取左：2 1-7=-5, 减dp[ 3][ 4 ]=0 → -5。 取右：2 2-7=-3, 减dp[ 2][ 3 ]=2 → -5。 max=-5 → dp[ 2][ 4 ]=-5。 len=4: [ 0,3]：S=prefix[ 4]-prefix[ 0 ]=13。 取左：2 5-13=-3, 减dp[ 1][ 3 ]=-1 → -3-(-1)=-2。 取右：2 4-13=-5, 减dp[ 0][ 2 ]=0 → -5。 max=-2 → dp[ 0][ 3 ]=-2。 [ 1,4]：S=prefix[ 5]-prefix[ 1 ]=15-5=10。 取左：2 3-10=-4, 减dp[ 2][ 4 ]=-5 → -4-(-5)=1。 取右：2 2-10=-6, 减dp[ 1][ 3 ]=-1 → -6-(-1)=-5。 max=1 → dp[ 1][ 4 ]=1。 len=5: [ 0,4]：S=prefix[ 5]-prefix[ 0 ]=15。 取左：2 5-15=-5, 减dp[ 1][ 4 ]=1 → -6。 取右：2 2-15=-11, 减dp[ 0][ 3 ]=-2 → -9。 max=-6 → dp[ 0][ 4 ]=-6。 dp[ 0][ 4] = -6 < 0，所以 Alice 净收益差值小于 Bob，Alice 输。 最终答案 对于 stones=[ 5,3,1,4,2 ]，Alice 无法获胜，返回 false。 复杂度分析 时间复杂度 O(n²)，空间复杂度 O(n²)（可优化为 O(n) 但没必要）。