LeetCode 1690题解：动态规划+前缀和求解区间最大差值（石头游戏VII）
一、题目解读
力扣1690题“石头游戏VII”（题目名称可能需补充）要求：给定整数数组stones，两人轮流从数组左右两端移除石头，得分等于移除部分的总和减去剩余部分的总和。求先手玩家能获得的最大得分差值。例如，数组[5,3,1,4,2]中，先手若移除左端5，剩余[3,1,4,2]，得分5-(3+1+4+2)=5-10=-5，需最大化此差值。题目本质是寻找最优区间分割策略，转化为数学优化问题。
二、解题思路
1. 前缀和预处理：计算数组前缀和prefix，便于O(1)获取任意区间和（避免重复累加）。
2. 动态规划定义：dp[i][j]表示区间stones[i..j]内的最大得分差值。
3. 状态转移方程：当前玩家可移除左/右端石头，剩余区间由后续玩家操作。例如，移除左端后，剩余和为prefix[j+1]-prefix[i+1]（右区间和），则当前差值为该和减去后续玩家在[i+1,j]内的最优得分（即dp[i+1][j]）。同理分析右端移除情况，取两者最大值。
4. 边界与递推：从小区间（len=2）逐步扩展至全局，确保子问题已解。
三、解题步骤
1. 计算前缀和：prefix[i+1]=prefix[i]+stones[i]，存储0~i元素总和。
2. 初始化DP数组：dp为n×n矩阵，初始值全0（因小区间可能无需分割）。
3. 动态规划循环：
外层循环：区间长度len=2→n（避免单元素区间无选择）。
内层循环：枚举起点i，终点j=i+len-1。
计算移除左/右端后的剩余和leftSum,rightSum，结合对应子区间的dp值，更新dp[i][j]=max(左端策略差值,右端策略差值)。
4. 结果：返回全局区间DP[0][n-1]的最大差值。
四、代码与注释
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];
}
};注释说明：
● prefix数组避免重复计算区间和，提升效率。
● dp定义确保状态转移的逻辑正确性，外层循环控制区间扩展，内层计算依赖已解子问题。
五、总结
本题通过动态规划将复杂的区间选择问题转化为子问题最优解的组合，前缀和的应用大幅降低计算复杂度。关键在于理解“当前决策影响后续状态”的DP本质，以及如何设计合理的状态转移方程。时间复杂度O(n²)，空间复杂度O(n²)，可进一步优化为O(n)空间（滚动数组）。掌握此类区间DP思路，对解决类似资源分配、序列优化问题具有重要启发。
原创内容 转载请注明出处
