Medium

题目描述

Alice 和 Bob 继续他们的石子游戏。现在有若干堆石子排成一行，每堆都有正整数颗石子 piles[i]。游戏的目标是得到最多的石子。

Alice 和 Bob 轮流行动，Alice 先开始。

在每个玩家的回合中，该玩家可以拿走剩余石子堆中前 X 堆的所有石子，其中 1 <= X <= 2M。然后，我们设定 M = max(M, X)。初始时，M = 1。

游戏一直持续到所有石子都被取完。

假设 Alice 和 Bob 都发挥出最佳水平，返回 Alice 能获得的最大石子数量。

示例 1：

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果 Alice 一开始拿一堆石子，Bob 拿两堆，然后 Alice 再拿 2 堆。Alice 可以得到 2 + 4 + 4 = 10 颗石子。
如果 Alice 一开始拿两堆石子，那么 Bob 可以拿走剩下的三堆。在这种情况下，Alice 得到 2 + 7 = 9 颗石子。
所以我们返回 10，因为这是更大的值。

示例 2：

输入：piles = [1,2,3,4,5,100]
输出：104

约束条件：

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10^4

解题思路

这是一个经典的博弈论动态规划问题。关键思路是：每个玩家都会选择对自己最优的策略。

分析思路：

  1. 状态定义：用 dp[i][m] 表示从第 i 堆开始，当前 M 值为 m 时，当前玩家能获得的最大石子数。

  2. 状态转移：当前玩家可以选择拿走前 x 堆石子（1 ≤ x ≤ 2m），拿走后：

    • 当前玩家得到 sum(piles[i:i+x]) 颗石子
    • 剩余石子由对手开始游戏，对手能得到 dp[i+x][max(m,x)] 颗石子
    • 当前玩家最终能得到的石子数 = 总剩余石子数 - 对手能得到的石子数

  3. 优化策略：当前玩家会选择使自己获得最多石子的方案，即： dp[i][m] = max(suffixSum[i] - dp[i+x][max(m,x)]) 其中 x ∈ [1, min(2m, n-i)]

  4. 边界条件：当 i >= n 时，没有石子可取，返回 0。

使用后缀和数组可以快速计算剩余石子总数，避免重复计算。记忆化搜索可以避免重复子问题的计算。

代码实现

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector<int> suffixSum(n + 1, 0);
        
        // 计算后缀和
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        
        // 记忆化数组
        vector<vector<int>> memo(n, vector<int>(n + 1, -1));
        
        function<int(int, int)> dfs = [&](int i, int m) -> int {
            if (i >= n) return 0;
            if (memo[i][m] != -1) return memo[i][m];
            
            int maxStones = 0;
            for (int x = 1; x <= min(2 * m, n - i); x++) {
                // 当前玩家拿走前x堆，剩余的让对手去拿
                int opponent = dfs(i + x, max(m, x));
                // 当前玩家能得到的石子数 = 总剩余石子数 - 对手能得到的石子数
                maxStones = max(maxStones, suffixSum[i] - opponent);
            }
            
            return memo[i][m] = maxStones;
        };
        
        return dfs(0, 1);
    }
};

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)
        
        # 计算后缀和
        suffix_sum = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + piles[i]
        
        # 记忆化装饰器
        from functools import lru_cache
        
        @lru_cache(None)
        def dfs(i, m):
            if i >= n:
                return 0
            
            max_stones = 0
            for x in range(1, min(2 * m, n - i) + 1):
                # 当前玩家拿走前x堆，剩余的让对手去拿
                opponent = dfs(i + x, max(m, x))
                # 当前玩家能得到的石子数 = 总剩余石子数 - 对手能得到的石子数
                max_stones = max(max_stones, suffix_sum[i] - opponent)
            
            return max_stones
        
        return dfs(0, 1)

public class Solution {
    public int StoneGameII(int[] piles) {
        int n = piles.Length;
        int[] suffixSum = new int[n + 1];
        
        // 计算后缀和
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }
        
        // 记忆化数组
        int[,] memo = new int[n, n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i, j] = -1;
            }
        }
        
        return Dfs(0, 1, suffixSum, memo, n);
    }
    
    private int Dfs(int i, int m, int[] suffixSum, int[,] memo, int n) {
        if (i >= n) return 0;
        if (memo[i, m] != -1) return memo[i, m];
        
        int maxStones = 0;
        for (int x = 1; x <= Math.Min(2 * m, n - i); x++) {
            // 当前玩家拿走前x堆，剩余的让对手去拿
            int opponent = Dfs(i + x, Math.Max(m, x), suffixSum, memo, n);
            // 当前玩家能得到的石子数 = 总剩余石子数 - 对手能得到的石子数
            maxStones = Math.Max(maxStones, suffixSum[i] - opponent);
        }
        
        return memo[i, m] = maxStones;
    }
}

var stoneGameII = function(piles) {
    const n = piles.length;
    const suffixSum = new Array(n + 1).fill(0);
    
    // 计算后缀和
    for (let i = n - 1; i >= 0; i--) {
        suffixSum[i] = suffixSum[i + 1] + piles[i];
    }
    
    // 记忆化缓存
    const memo = new Map();
    
    const dfs = (i, m) => {
        if (i >= n) return 0;
        
        const key = `${i}-${m}`;
        if (memo.has(key)) return memo.get(key);
        
        let maxStones = 0;
        for (let x = 1; x <= Math.min(2 * m, n - i); x++) {
            // 当前玩家拿走前x堆，剩余的让对手去拿
            const opponent = dfs(i + x, Math.max(m, x));
            // 当前玩家能得到的石子数 = 总剩余石子数 - 对手能得到的石子数
            maxStones = Math.max(maxStones, suffixSum[i] - opponent);
        }
        
        memo.set(key, maxStones);
        return maxStones;
    };
    
    return dfs(0, 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n³) - 状态数为 O(n²)，每个状态的转移需要 O(n) 时间
空间复杂度O(n²) - 记忆化数组的空间开销

相关题目