当前位置:首页 > 力扣 > LeetCode 1690题解:动态规划+前缀和求解区间最大差值(石头游戏VII)

LeetCode 1690题解:动态规划+前缀和求解区间最大差值(石头游戏VII)

2个月前 (07-16)

LeetCode 1690题解:动态规划+前缀和求解区间最大差值(石头游戏VII) 动态规划 前缀和 区间DP 石头游戏VII 力扣题解 C++ 第1张

一、题目解读

力扣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思路,对解决类似资源分配、序列优化问题具有重要启发。


原创内容 转载请注明出处

分享给朋友:

相关文章

NOIP2005 普及组 洛谷P1408 背包问题的空间优化技巧与实战应用

NOIP2005 普及组 洛谷P1408 背包问题的空间优化技巧与实战应用

题目重解想象你是一名药师,有t分钟在山上采集m种草药。每种草药需要time分钟采集,价值为num。这就像考试时分配时间做题,要选择收益最大的题目组合。题目要求计算在规定时间内能获得的最大草药价值。解题...

力扣540题:线性扫描法如何高效定位唯一数

力扣540题:线性扫描法如何高效定位唯一数

题目重解一个严格递增的有序数组中,除某个元素外,其余每个元素均出现两次。这个看似简单的条件背后隐藏着巧妙的规律——单一元素会打破数组的"成对对称性"。题目要求以O(log n)时间...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

2022 CSP-J 上升点序(洛谷P8816)解题报告:动态规划求解最长上升序列

2022 CSP-J 上升点序(洛谷P8816)解题报告:动态规划求解最长上升序列

一、题目解读2022年CSP-J题目“上升点序”(洛谷P8816)要求给定一个平面点集,每个点的坐标(x,y)均为整数。题目需要构造一个最长的上升序列,序列中相邻点的坐标满足x和y均严格递增。允许使用...

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

牛客网288555题解题指南:动态规划求解小红的暑假(附代码解析)

一、题目解读牛客网288555题要求解决一个组合数学问题:有三位朋友,每天需邀请其中一位参加聚会,但不能连续两天邀请同一位朋友。给定天数n,求满足条件的不同邀请方案总数。题目考察动态规划、状态转移及组...

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

【蓝桥杯国赛A组】冰山体积计算:动态规划与map统计的解题方案(洛谷P8767)

一、题目解读本题为2021年蓝桥杯国赛A组题目“冰山”(洛谷P8767),要求处理冰山在融化与新生成过程中的体积变化。每日存在两种操作:冰山体积按固定值x融化(体积不足x的部分视为完全融化),以及新增...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。