【算法日记】Day 10 动态规划专题——区间DP之基于两侧端点的讨论

张开发
• 2026/4/10 9:02:35 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 10 动态规划专题——区间DP之基于两侧端点的讨论
Abstract#动态规划#区间DP#博弈1. 题目题目LeetCode 486. 预测赢家核心思路两人轮流从数组两端取数最终分数高者赢。定义f(l, r)表示在子数组nums[l…r]中当前先手玩家能获得的最大分数。转移时若取左端nums[l]则对手会在[l1, r]中成为先手且对手会采取最优策略使当前玩家后续得分最小所以当前玩家总得分为nums[l] min(f(l1, r-1), f(l2, r))取右端同理。最终先手得分first f(0, n-1)后手得分second sum - first若first second则先手赢。复杂度时间复杂度O ( n 2 ) O(n²)O(n2)空间复杂度O ( n 2 ) O(n²)O(n2)可空间压缩至O ( n ) O(n)O(n)。2. 代码classSolution{public:intf(vectorintnums,vectorvectorintdp,intl,intr){if(dp[l][r]!-1)returndp[l][r];intnnums.size(),ans;if(lr)ansnums[l];elseif(lr-1)ansmax(nums[l],nums[r]);else{intp1nums[l]min(f(nums,dp,l1,r-1),f(nums,dp,l2,r));intp2nums[r]min(f(nums,dp,l1,r-1),f(nums,dp,l,r-2));ansmax(p1,p2);}dp[l][r]ans;returnans;}boolpredictTheWinner(vectorintnums){intsum0;for(autonum:nums){sumnum;}vectorvectorintdp(25,vectorint(25,-1));intfirstf(nums,dp,0,nums.size()-1);intsecondsum-first;returnfirstsecond?true:false;}};3. 心得区间DP思想将大范围问题拆解成若干小范围上的问题求解这里的小范围问题是大范围问题的重叠子问题。这种拆解方法总是基于分情况讨论的思想而得出的就区间DP而言有两种讨论思路一是基于两侧端点的可能性展开如本题无论是从情景还是从分析过程都是在左右两侧端点操作的二是基于范围中的划分点展开具体题目见明日再学。博弈DP中的min理解当前玩家取走一个数后对手在剩余区间成为先手且对手会最大化自己的分数等价于让当前玩家在后续中得到尽可能小的分数。因此转移时要取min而不是max。4. 相关题目LeetCode 1312. 让字符串成为回文串的最少插入次数

更多文章