前缀和优化动态规划：从原理到实战-平芜编程栈

1. 引言

动态规划（Dynamic Programming，DP）是算法竞赛和面试中的高频考点，而前缀和（Prefix Sum）则是一种经典的预处理技巧。当两者结合时，往往能显著降低时间复杂度，把原本需要 O(n²) 甚至 O(n³) 的转移优化到 O(n) 或 O(n²)。本文将从前缀和的基本思想出发，结合具体例题，系统讲解前缀和优化 DP 的适用场景、推导方法和代码实现。

2. 前缀和基础回顾

前缀和的核心思想是：用一个数组pre[i]记录原数组前 i 项的和，从而在 O(1) 时间内求出任意区间[l, r]的和。

vector<int> 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; vector<pair<int, int>> pts(n); // (x, w) for (int i = 0; i < n; i++) { cin >> pts[i].first >> pts[i].second; } sort(pts.begin(), pts.end()); vector<int> 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; }