Hard

题目描述

有几块石子排成一行，每块石子都有一个关联的值，这个值是一个整数，保存在数组 stoneValue 中。

游戏中的每一轮：Alice 会将这行石子分成两个非空行（即，左侧行和右侧行），接着 Bob 负责计算每一行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分增加为剩余行中所有石子值的总和。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩余的行开始。

只剩下一块石子时，游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

示例 1：

输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行分为 [6,2,3]，[4,5,5]。左行的值是 11，右行的值是 14。Bob 丢弃了右行，Alice 的分数现在是 11。
在第二轮中，Alice 将行分为 [6]，[2,3]。这次 Bob 丢弃了左行，Alice 的分数变成了 16 (11 + 5)。
最后一轮 Alice 只能将行分为 [2]，[3]。Bob 丢弃了右行，Alice 的分数现在是 18 (16 + 2)。由于行中只剩下一块石子，所以游戏结束。

示例 2：

输入：stoneValue = [7,7,7,7,7,7,7]
输出：28

示例 3：

输入：stoneValue = [4]
输出：0

提示：

  • 1 <= stoneValue.length <= 500
  • 1 <= stoneValue[i] <= 10^6

解题思路

这是一道博弈论与动态规划结合的问题。我们需要找出 Alice 能够获得的最大分数。

核心思路：

  1. 状态定义：设 dp[i][j] 表示在区间 [i, j] 内 Alice 能获得的最大分数。

  2. 转移方程：对于区间 [i, j]，Alice 需要选择一个分割点 k（i <= k < j），将区间分为 [i, k] 和 [k+1, j] 两部分。

    • 计算左半部分和右半部分的石子值总和
    • Bob 会丢弃值较大的部分，Alice 获得值较小部分的分数
    • 如果两部分值相等，Alice 可以选择保留任意一部分
    • 继续在保留的部分进行游戏

  3. 优化策略：

    • 使用前缀和快速计算区间和
    • 对于每个分割点，比较左右两部分的和，选择较小的一部分作为 Alice 当前轮的得分
    • 然后递归计算在该部分继续游戏能获得的分数

  4. 边界条件：当区间只有一个元素时，无法分割，得分为 0。

时间复杂度为 O(n³)，空间复杂度为 O(n²)，其中 n 是石子数量。通过记忆化搜索避免重复计算相同的子问题。

代码实现

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
        }
        
        vector<vector<int>> memo(n, vector<int>(n, -1));
        
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i == j) return 0;
            if (memo[i][j] != -1) return memo[i][j];
            
            int result = 0;
            for (int k = i; k < j; k++) {
                int leftSum = prefixSum[k + 1] - prefixSum[i];
                int rightSum = prefixSum[j + 1] - prefixSum[k + 1];
                
                if (leftSum < rightSum) {
                    result = max(result, leftSum + dfs(i, k));
                } else if (leftSum > rightSum) {
                    result = max(result, rightSum + dfs(k + 1, j));
                } else {
                    result = max(result, max(leftSum + dfs(i, k), rightSum + dfs(k + 1, j)));
                }
            }
            
            return memo[i][j] = result;
        };
        
        return dfs(0, n - 1);
    }
};

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        n = len(stoneValue)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stoneValue[i]
        
        @lru_cache(None)
        def dfs(i, j):
            if i == j:
                return 0
            
            result = 0
            for k in range(i, j):
                left_sum = prefix_sum[k + 1] - prefix_sum[i]
                right_sum = prefix_sum[j + 1] - prefix_sum[k + 1]
                
                if left_sum < right_sum:
                    result = max(result, left_sum + dfs(i, k))
                elif left_sum > right_sum:
                    result = max(result, right_sum + dfs(k + 1, j))
                else:
                    result = max(result, max(left_sum + dfs(i, k), right_sum + dfs(k + 1, j)))
            
            return result
        
        return dfs(0, n - 1)

public class Solution {
    public int StoneGameV(int[] stoneValue) {
        int n = stoneValue.Length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
        }
        
        int[,] memo = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                memo[i, j] = -1;
            }
        }
        
        return Dfs(0, n - 1, prefixSum, memo);
    }
    
    private int Dfs(int i, int j, int[] prefixSum, int[,] memo) {
        if (i == j) return 0;
        if (memo[i, j] != -1) return memo[i, j];
        
        int result = 0;
        for (int k = i; k < j; k++) {
            int leftSum = prefixSum[k + 1] - prefixSum[i];
            int rightSum = prefixSum[j + 1] - prefixSum[k + 1];
            
            if (leftSum < rightSum) {
                result = Math.Max(result, leftSum + Dfs(i, k, prefixSum, memo));
            } else if (leftSum > rightSum) {
                result = Math.Max(result, rightSum + Dfs(k + 1, j, prefixSum, memo));
            } else {
                result = Math.Max(result, Math.Max(leftSum + Dfs(i, k, prefixSum, memo), 
                                                  rightSum + Dfs(k + 1, j, prefixSum, memo)));
            }
        }
        
        return memo[i, j] = result;
    }
}

var stoneGameV = function(stoneValue) {
    const n = stoneValue.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
    }

    const memo = new Array(n).fill(null).map(() => new Array(n).fill(-1));

    function dp(left, right) {
        if (left === right) return 0;
        if (memo[left][right] !== -1) return memo[left][right];

        let maxScore = 0;
        for (let k = left; k < right; k++) {
            const leftSum = prefixSum[k + 1] - prefixSum[left];
            const rightSum = prefixSum[right + 1] - prefixSum[k + 1];

            if (leftSum < rightSum) {
                maxScore = Math.max(maxScore, leftSum + dp(left, k));
            } else if (leftSum > rightSum) {
                maxScore = Math.max(maxScore, rightSum + dp(k + 1, right));
            } else {
                maxScore = Math.max(maxScore,
                    leftSum + dp(left, k),
                    rightSum + dp(k + 1, right)
                );
            }
        }

        memo[left][right] = maxScore;
        return maxScore;
    }

    return dp(0, n - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n³)
空间复杂度O(n²)

其中 n 是石子数组的长度。时间复杂度 O(n³) 来自于三层循环：外层是区间长度，中层是起始位置，内层是分割点。空间复杂度 O(n²) 用于存储记忆化数组和前缀和数组。

相关题目