Medium

题目描述

Alice 和 Bob 轮流玩一个游戏，Alice 先开始。

有 n 个石子排成一排。每个玩家的回合中，可以从行的 最左边 或 最右边 移除一个石子，并获得与该行中剩余石子值之和相等的分数。当没有石子可移除时，得分较高者获胜。

Bob 发现他总是会输掉游戏（可怜的 Bob，他总是输），所以他决定尽力 减小得分的差值。Alice 的目标是最大化得分的差值。

给你一个整数数组 stones，其中 stones[i] 表示 从左边开始 第 i 个石子的值，请返回在双方都采用最优策略的情况下，Alice 和 Bob 的得分差值。

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- Alice 移除 2，得到 5 + 3 + 1 + 4 = 13 分。Alice = 13，Bob = 0，stones = [5,3,1,4]
- Bob 移除 5，得到 3 + 1 + 4 = 8 分。Alice = 13，Bob = 8，stones = [3,1,4]
- Alice 移除 3，得到 1 + 4 = 5 分。Alice = 18，Bob = 8，stones = [1,4]
- Bob 移除 1，得到 4 分。Alice = 18，Bob = 12，stones = [4]
- Alice 移除 4，得到 0 分。Alice = 18，Bob = 12，stones = []
得分差值为 18 - 12 = 6

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

提示：

  • n == stones.length
  • 2 <= n <= 1000
  • 1 <= stones[i] <= 1000

解题思路

这是一个经典的区间动态规划问题。关键在于理解游戏规则：移除一个石子后，得分等于剩余石子的和。

核心思路：

  1. 使用 dp[i][j] 表示在区间 [i, j] 中，当前玩家相对于对手能获得的最大得分差值
  2. 当前玩家可以选择移除左端点 i 或右端点 j 的石子
    • 移除左端点：得到区间 [i+1, j] 的和，然后对手在 [i+1, j] 中游戏
    • 移除右端点：得到区间 [i, j-1] 的和，然后对手在 [i, j-1] 中游戏
  3. 状态转移方程：dp[i][j] = max(sum[i+1][j] - dp[i+1][j], sum[i][j-1] - dp[i][j-1])
  4. 使用前缀和优化区间求和操作

优化细节：

  • 使用前缀和数组快速计算区间和
  • 从小区间开始计算，逐步扩展到大区间
  • 最终答案为 dp[0][n-1]，表示在整个数组上 Alice 相对于 Bob 的得分差值

时间复杂度为 O(n²)，空间复杂度为 O(n²)，满足题目约束条件。

代码实现

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                int sumLeft = prefixSum[j + 1] - prefixSum[i + 1];
                int sumRight = prefixSum[j] - prefixSum[i];
                dp[i][j] = max(sumLeft - dp[i + 1][j], sumRight - dp[i][j - 1]);
            }
        }
        
        return dp[0][n - 1];
    }
};

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        
        dp = [[0] * n for _ in range(n)]
        
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                sum_left = prefix_sum[j + 1] - prefix_sum[i + 1]
                sum_right = prefix_sum[j] - prefix_sum[i]
                dp[i][j] = max(sum_left - dp[i + 1][j], sum_right - dp[i][j - 1])
        
        return dp[0][n - 1]

public class Solution {
    public int StoneGameVII(int[] stones) {
        int n = stones.Length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stones[i];
        }
        
        int[,] dp = new int[n, n];
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                int sumLeft = prefixSum[j + 1] - prefixSum[i + 1];
                int sumRight = prefixSum[j] - prefixSum[i];
                dp[i, j] = Math.Max(sumLeft - dp[i + 1, j], sumRight - dp[i, j - 1]);
            }
        }
        
        return dp[0, n - 1];
    }
}

var stoneGameVII = function(stones) {
    const n = stones.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + stones[i];
    }
    
    const dp = Array.from({ length: n }, () => new Array(n).fill(0));
    
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            const sumLeft = prefixSum[j + 1] - prefixSum[i + 1];
            const sumRight = prefixSum[j] - prefixSum[i];
            dp[i][j] = Math.max(sumLeft - dp[i + 1][j], sumRight - dp[i][j - 1]);
        }
    }
    
    return dp[0][n - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要填充 n×n 的 dp 表，每个状态计算需要 O(1) 时间
空间复杂度O(n²)dp 数组占用 O(n²) 空间，前缀和数组占用 O(n) 空间

相关题目