前缀和优化动态规划：从原理到实战-北京尧图网络

1. 引言动态规划Dynamic ProgrammingDP是算法竞赛和面试中的高频考点而前缀和Prefix Sum则是一种经典的预处理技巧。当两者结合时往往能显著降低时间复杂度把原本需要 O(n²) 甚至 O(n³) 的转移优化到 O(n) 或 O(n²)。本文将从前缀和的基本思想出发结合具体例题系统讲解前缀和优化 DP 的适用场景、推导方法和代码实现。2. 前缀和基础回顾前缀和的核心思想是用一个数组pre[i]记录原数组前 i 项的和从而在 O(1) 时间内求出任意区间[l, r]的和。vectorint pre(n 1, 0); for (int i 1; i n; i) { pre[i] pre[i - 1] a[i]; } // 区间 [l, r] 的和 pre[r] - pre[l - 1]在 DP 优化中我们通常不是直接使用一维前缀和而是把「前缀最值」「前缀和」等结构应用到状态转移方程中从而跳过内层循环。3. 前缀和优化 DP 的核心思想很多 DP 的状态转移方程具有如下形式dp[i] max/min ( f(j) cost(j, i) )其中 j 属于某个区间 [L, R]如果cost(j, i)可以拆分成「只与 j 有关的部分」和「只与 i 有关的部分」那么我们就可以把「只与 j 有关的部分」预处理成前缀最值或前缀和从而把内层枚举 j 的循环优化掉。具体来说当转移方程可以写成dp[i] g(i) max/min ( h(j) )j ∈ [L, R]时我们只需要维护h(j)在区间[L, R]上的前缀最值或前缀和即可在 O(1) 时间内完成单次转移。4. 经典例题一最大子段和最大子段和是最简单的前缀和优化 DP 例子。设dp[i]表示以第 i 个元素结尾的最大子段和则有dp[i] max(a[i], dp[i - 1] a[i])这个方程本身已经是 O(1) 转移不需要优化。但我们可以换一个角度理解dp[i] pre[i] - min(pre[j])其中 j ∈ [0, i - 1]这里pre[j]的最小值可以边遍历边维护因此整体复杂度为 O(n)。这种「维护前缀最值」的思路正是前缀和优化 DP 的雏形。5. 经典例题二划分数组求最小代价给定一个长度为 n 的数组要求将其划分为若干段每段的代价为段内元素和的平方求最小总代价。设dp[i]表示前 i 个元素划分完毕的最小代价则dp[i] min( dp[j] (pre[i] - pre[j])² )j ∈ [0, i - 1]展开后得到dp[i] pre[i]² min( dp[j] pre[j]² - 2 * pre[i] * pre[j] )如果直接枚举 j复杂度为 O(n²)。但注意到dp[j] pre[j]²只与 j 有关而-2 * pre[i] * pre[j]同时包含 i 和 j无法直接使用前缀最值。此时需要引入斜率优化Convex Hull Trick这已经超出了前缀和优化的范畴。因此前缀和优化适用于「交叉项可以分离」的方程而斜率优化适用于「交叉项无法分离」的方程。6. 经典例题三区间内选点问题给定 n 个点每个点有坐标x[i]和权值w[i]要求选择若干点使得任意两个被选点之间的距离不小于 K求最大权值和。设dp[i]表示前 i 个点中选择第 i 个点时的最大权值和则dp[i] w[i] max( dp[j] )其中 x[j] x[i] - K这里max(dp[j])的 j 范围是一个前缀区间我们可以用前缀最大值数组best[i]来维护best[i] max(best[i - 1], dp[i])然后通过二分查找找到满足x[j] x[i] - K的最大下标 j即可在 O(log n) 时间内完成单次转移整体复杂度 O(n log n)。7. 前缀和优化 DP 的适用条件总结综合以上例题前缀和优化 DP 通常需要满足以下条件转移方程呈区间枚举形式内层循环枚举的 j 来自一个连续区间。代价函数可分离cost(j, i)能拆成f(j) g(i)的形式交叉项不存在或可以单独处理。区间端点单调随着 i 增大j 的可行区间也单调移动便于用前缀结构维护。如果交叉项无法分离则需要考虑斜率优化或四边形不等式优化如果区间端点不单调则需要使用线段树或树状数组维护。8. 代码模板下面给出一个通用的前缀和优化 DP 模板以「区间内选点问题」为例#include bits/stdc.h using namespace std; int main() { int n, K; cin n K; vectorpairint, int pts(n); // (x, w) for (int i 0; i n; i) { cin pts[i].first pts[i].second; } sort(pts.begin(), pts.end()); vectorint dp(n, 0), best(n, 0); for (int i 0; i n; i) { // 二分查找第一个 x[j] x[i] - K 的位置 int lo 0, hi i - 1, pos -1; while (lo hi) { int mid (lo hi) / 2; if (pts[mid].first pts[i].first - K) { pos mid; lo mid 1; } else { hi mid - 1; } } dp[i] pts[i].second (pos 0 ? best[pos] : 0); best[i] max(i 0 ? best[i - 1] : 0, dp[i]); } cout best[n - 1] endl; return 0; }9. 总结前缀和优化 DP 的核心在于「把内层枚举转化为前缀查询」。当转移方程中的代价函数可以分离、且 j 的可行区间单调时用前缀和或前缀最值数组即可把 O(n²) 优化到 O(n) 或 O(n log n)。掌握这一技巧需要多做练习熟悉「拆项—分离—前缀维护」三步走的推导流程。

前缀和优化动态规划：从原理到实战

相关推荐

技术团队知识沉淀：从重复踩坑到经验复用的工程实践

基于GAN的可再生能源场景生成：两个互连深度神经网络的对抗博弈

上市公司投资者关系（IR）网站怎么建？内容架构、合规要点与运维指南

更多资讯

利川哪里有考电工证多久拿证外省证书能转过来吗

四川省电工证怎样注销千万别踩坑怎么操作

高极电工证试题怎么查网上查询？实操考试心里没底怕挂科

工地太忙根本没时间复习考试？考上电工证是什么文凭还能全国通用

电工证怎么考肇庆封开千万别踩坑，考前这些细节不看后悔

平谷电工证报名时间官方报名入口怎么找

今日更新

高压电工证哪里可以挂多久拿证全攻略：实操考试心里没底怕挂科别慌

电工证的理论题目在哪考，外省证怎么转过来

工地太忙根本没时间复习考试，职业学校的电工证值不值得考？

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？