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)。掌握这一技巧需要多做练习熟悉「拆项—分离—前缀维护」三步走的推导流程。