【算法日记】Day 12 动态规划专题——区间DP之综合情况讨论

张开发
• 2026/4/11 22:00:05 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【算法日记】Day 12 动态规划专题——区间DP之综合情况讨论
Abstract#动态规划#区间DP#前缀和1. 题目题目LeetCode 1000. 合并石头的最低成本核心思路将k堆相邻石子合并成一堆每次合并的成本为这k堆石子的总数。首先最终能否合并成一堆取决于(n-1) % (k-1) 0。筛掉不能合成一堆的情况之后使用区间DP定义dp[l][r]表示将区间[l, r]的石子合并成最少堆数尽量少但需满足后续可合并的最小成本。转移时讨论在左侧能合成一堆的情况。当(r-l) % (k-1) 0时表示整个区间最终能合并成一堆此时加上区间和作为最后一次合并的成本否则只是转移到枚举中的最小值情况。复杂度时间复杂度O ( n 3 ) O(n^3)O(n3)空间复杂度O ( n 2 ) O(n^2)O(n2)。2. 代码classSolution{public:intmergeStones(vectorintstones,intk){intnstones.size();if((n-1)%(k-1)!0)return-1;vectorintpre(n1,0);for(inti1;in;i){pre[i]pre[i-1]stones[i-1];}vectorvectorintdp(n,vectorint(n,0));for(intln-2;l0;--l){for(intrl1;rn;r){intans0x3f3f3f3f;for(intml;mr;mk-1){ansmin(ans,dp[l][m]dp[m1][r]);}if((r-l)%(k-1)0)anspre[r1]-pre[l];dp[l][r]ans;}}returndp[0][n-1];}};3. 心得可行性判断(n-1) % (k-1) ! 0直接返回-1。因为每次合并减少k-1堆从n堆到1堆需要减少n-1堆所以必须整除。区间 DP 的步长枚举合并时只能合并相邻的k堆但通过多次合并最终区间可以分解为若干个子区间每个子区间独立合并成一堆。因此枚举分割点 m 时m k-1确保了左侧石堆始终能合成一堆。是否能合成一堆的不同情况的处理只有当区间长度r-l是k-1的倍数时整个区间才能最终合并成一堆此时需要加上区间和作为最后一次合并的成本。4. 相关题目LeetCode 546. 移除盒子 —— 复杂区间DP

更多文章