力扣1690题详解：动态规划解石子游戏VII

一、问题描述

石子游戏VII是一个双人博弈问题。给定一排石子，每个石子有一个价值。两位玩家轮流从最左或最右端取走一块石子，直到没有石子剩余。每位玩家的得分是所取石子价值的总和。游戏目标是使自己的得分尽可能比对手高。题目要求计算先手玩家能获得的最大得分差。

二、解题思路

这道题可以使用动态规划(DP)来解决，核心思想是：

1. 使用前缀和数组快速计算任意区间的和

2. 定义dp[i][j]表示在stones[i..j]区间内当前玩家能获得的最大得分差

3. 采用自底向上的方法，先计算小区间，再推导大区间

三、完整代码解析

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        int n = stones.size();
        vector<int> prefix(n + 1, 0);
        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + stones[i];
        }
        
        // dp[i][j]表示在stones[i..j]区间内的最大差值
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 从小区间到大区间逐步计算
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                // 移除左边石头后的剩余和
                int leftSum = prefix[j + 1] - prefix[i + 1];
                // 移除右边石头后的剩余和
                int rightSum = prefix[j] - prefix[i];
                
                // 当前玩家可以选择移除左边或右边，取最大差值
                dp[i][j] = max(leftSum - dp[i + 1][j], rightSum - dp[i][j - 1]);
            }
        }
        
        return dp[0][n - 1];
    }
};

四、关键点详解

1. 前缀和数组

前缀和数组prefix的构建使得我们可以快速计算任意子数组的和：

• prefix[i]表示前i个元素的和

• 区间[i,j]的和可以通过prefix[j+1]-prefix[i]计算得到

2. DP数组定义

dp[i][j]表示当石子剩下stones[i..j]时，当前玩家能获得的最大得分差。这个定义是解决博弈类DP问题的关键。

3. 状态转移方程

对于每个区间[i,j]，玩家有两种选择：

1. 拿走左边的石头：获得prefix[j+1]-prefix[i+1]的分数，然后对手在[i+1,j]区间操作

2. 拿走右边的石头：获得prefix[j]-prefix[i]的分数，然后对手在[i,j-1]区间操作

状态转移方程为：

dp[i][j] = max(
    (剩余和取左) - dp[i+1][j], 
    (剩余和取右) - dp[i][j-1]
)

4. 计算顺序

采用区间长度递增的顺序计算：

• 先计算所有长度为2的区间

• 然后计算长度为3的区间，依此类推

• 最终dp[0][n-1]就是整个问题的解

五、总结

这道题展示了如何将博弈问题转化为动态规划问题。关键在于：

1. 正确定义DP状态

2. 合理使用前缀和优化计算

3. 采用自底向上的计算顺序

4. 理解状态转移方程的含义

通过这种解法，我们不仅解决了这道题，也为类似的区间DP和博弈问题提供了解决思路。