算法概述
斜率优化动态规划（Slope Trick / Convex Hull Trick for DP）是一种用于优化特定形式动态规划转移的高级技巧。当DP转移方程形如：
dp[i] = min{dp[j] + cost(j, i)} for j < i
且cost函数可以分解为与j相关的项、与i相关的项以及j和i的乘积项时，可以将问题转化为平面上的点集和斜率查询问题，利用单调性维护下凸壳，将每轮转移从O(n)优化到O(1)或O(log n)。
该技巧在区间DP、资源分配、最优调度等问题中有广泛应用，是竞赛编程中从O(n²)到O(n)或O(n log n)的关键优化手段。
核心原理
可优化DP的形式
考虑形如以下的转移方程：
dp[i] = min_{j < i} { dp[j] + a[i] * b[j] }
其中a[i]关于i单调，b[j]关于j单调。将其变形：
dp[i] = min_{j < i} { b[j] * a[i] + dp[j] }
对于固定的j，这是关于变量a[i]的一次函数：y = kx + b，其中k = b[j]，b = dp[j]。
几何解释
将每个决策点j视为直线L_j(x) = b[j] * x + dp[j]。求dp[i]等价于在x = a[i]处查询所有直线的最小值。
若b[j]单调递减，则新加入直线的斜率递减，有用的直线构成一个下凸壳。利用单调性，可以用双端队列维护凸壳，均摊O(1)查询。
凸壳维护
对于三条直线L1, L2, L3（斜率递减），L2无用的充要条件是L1与L2的交点横坐标 ≥ L2与L3的交点横坐标。
交点横坐标公式：x = (b3 – b1) / (k1 – k3)
Java完整实现
import java.util.*;
/**
* 斜率优化动态规划（凸包技巧）
* 用于优化形如 dp[i] = min{dp[j] + a[i]*b[j]} 的转移方程
*/
public class SlopeOptimizationDP {
/**
* 表示一条直线：y = k * x + b
*/
static class Line {
long k; // 斜率
long b; // 截距
Line(long k, long b) {
this.k = k;
this.b = b;
}
// 在x处求值
long eval(long x) {
return k * x + b;
}
// 与另一条直线的交点横坐标（用于比较）
// 返回 (other.b - this.b) / (this.k - other.k) 的分数形式
// 使用交叉相乘避免浮点
}
/**
* 单调队列维护下凸壳（斜率单调递减版本）
*/
static class ConvexHullTrick {
Deque<Line> hull = new ArrayDeque<>();
// 判断l1, l2, l3是否使得l2无用
// 条件：intersection(l1,l2) >= intersection(l2,l3)
// 即 (b2-b1)/(k1-k2) >= (b3-b2)/(k2-k3)
// 交叉相乘（注意斜率递减，分母为负，不等号方向变化）
private boolean isBad(Line l1, Line l2, Line l3) {
// (l2.b - l1.b) * (l2.k - l3.k) >= (l3.b - l2.b) * (l1.k - l2.k)
// 使用BigInteger避免溢出，或使用double近似
return (double)(l2.b - l1.b) / (l1.k - l2.k) >=
(double)(l3.b - l2.b) / (l2.k - l3.k);
}
// 添加新直线（斜率必须单调递减）
void addLine(long k, long b) {
Line newLine = new Line(k, b);
// 移除尾部无用直线
while (hull.size() >= 2) {
Line last = hull.pollLast();
Line secondLast = hull.peekLast();
if (!isBad(secondLast, last, newLine)) {
hull.addLast(last);
break;
}
// 继续弹出，last被确认为无用
}
hull.addLast(newLine);
}
// 查询最小值（x单调递增版本，均摊O(1)）
long queryMin(long x) {
while (hull.size() >= 2) {
Line first = hull.pollFirst();
Line second = hull.peekFirst();
if (first.eval(x) <= second.eval(x)) {
hull.addFirst(first);
break;
}
// first在x处不是最优，永久移除
}
return hull.peekFirst().eval(x);
}
// 通用查询（x不单调，二分O(log n)）
long queryMinBinary(long x) {
int lo = 0, hi = hull.size() - 1;
List<Line> lines = new ArrayList<>(hull);
while (lo < hi) {
int mid = (lo + hi) / 2;
if (lines.get(mid).eval(x) <= lines.get(mid + 1).eval(x)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lines.get(lo).eval(x);
}
}
/**
* 经典问题：批量生产调度
* 有n个任务，每个任务有加工时间t[i]和费用系数f[i]
* 将任务分批处理，每批的完成时间为该批最后一个任务的完成时间
* 每批费用 = 完成时间 * 该批所有任务的f之和 + 启动费用S
* 求最小总费用
*
* dp[i] = min_{j < i} { dp[j] + S * (sumF[n] - sumF[j]) + sumT[i] * (sumF[i] - sumF[j]) }
*
* 变形为：dp[i] = min { dp[j] - S*sumF[j] - sumT[i]*sumF[j] } + 常数项
* 即：dp[i] = min { (-sumF[j]) * sumT[i] + (dp[j] - S*sumF[j]) } + 常数
*/
public static long solveBatchScheduling(long[] t, long[] f, long S) {
int n = t.length;
long[] sumT = new long[n + 1];
long[] sumF = new long[n + 1];
for (int i = 1; i <= n; i++) {
sumT[i] = sumT[i - 1] + t[i - 1];
sumF[i] = sumF[i - 1] + f[i - 1];
}
long[] dp = new long[n + 1];
dp[0] = 0;
ConvexHullTrick cht = new ConvexHullTrick();
// 初始直线：k = -sumF[0] = 0, b = dp[0] - S*sumF[0] = 0
cht.addLine(0, 0);
for (int i = 1; i <= n; i++) {
// x = sumT[i]，查询最小值
long best = cht.queryMin(sumT[i]);
dp[i] = best + S * sumF[n] + sumT[i] * sumF[i];
// 添加新决策点j=i对应的直线
// k = -sumF[i], b = dp[i] - S*sumF[i]
// 注意：这里需要确认斜率单调性
long k = -sumF[i];
long b = dp[i];
cht.addLine(k, b);
}
return dp[n];
}
/**
* 经典问题2：玩具装箱（Toy Packaging）
* n个玩具，第i个玩具长度为c[i]
* 将它们装入容器，每段[i,j]的费用为 (j-i + sum(c[i..j]) - L)^2
* 求最小总费用
*
* 设sum[i]为前缀和，dp[i]表示装完前i个的最小费用
* dp[i] = min_{j < i} { dp[j] + (sum[i] - sum[j] + i - j - 1 - L)^2 }
*
* 令 A[i] = sum[i] + i, B[j] = sum[j] + j + 1 + L
* dp[i] = min { dp[j] + (A[i] - B[j])^2 }
* 展开后：dp[i] = min { dp[j] + B[j]^2 - 2*A[i]*B[j] } + A[i]^2
* 即：查询直线 y = (-2*B[j]) * x + (dp[j] + B[j]^2)，x = A[i]
*/
public static long solveToyPackaging(long[] c, long L) {
int n = c.length;
long[] sum = new long[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + c[i - 1];
}
long[] dp = new long[n + 1];
ConvexHullTrick cht = new ConvexHullTrick();
// j=0: B[0] = sum[0] + 0 + 1 + L = 1 + L
long B0 = 1 + L;
cht.addLine(-2 * B0, B0 * B0); // 初始直线
for (int i = 1; i <= n; i++) {
long A = sum[i] + i;
long best = cht.queryMin(A);
dp[i] = best + A * A;
long B = sum[i] + i + 1 + L;
cht.addLine(-2 * B, dp[i] + B * B);
}
return dp[n];
}
/**
* 经典问题3：单调队列优化DP — 双端队列版本
* 对于滑动窗口最小值问题
*/
public static long[] slidingWindowMin(long[] arr, int k) {
int n = arr.length;
long[] result = new long[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // 存储下标，维护单调递增
for (int i = 0; i < n; i++) {
// 移除窗口外的元素
while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
deque.pollFirst();
}
// 移除比当前元素大的元素（它们不会再成为最小值）
while (!deque.isEmpty() && arr[deque.peekLast()] >= arr[i]) {
deque.pollLast();
}
deque.addLast(i);
// 记录窗口最小值
if (i >= k - 1) {
result[i - k + 1] = arr[deque.peekFirst()];
}
}
return result;
}
/**
* 主程序：测试斜率优化DP
*/
public static void main(String[] args) {
System.out.println("===== 斜率优化动态规划（凸包技巧） =====\n");
// 测试1：批量生产调度
System.out.println("--- 测试1：批量生产调度 ---");
long[] t1 = {1, 3, 4, 2, 1};
long[] f1 = {3, 2, 3, 3, 4};
long S1 = 5;
long result1 = solveBatchScheduling(t1, f1, S1);
System.out.println("任务时间: " + Arrays.toString(t1));
System.out.println("费用系数: " + Arrays.toString(f1));
System.out.println("启动费用: " + S1);
System.out.println("最小总费用: " + result1);
// 测试2：玩具装箱
System.out.println("\n--- 测试2：玩具装箱 ---");
long[] c2 = {3, 4, 5, 6};
long L2 = 10;
long result2 = solveToyPackaging(c2, L2);
System.out.println("玩具长度: " + Arrays.toString(c2));
System.out.println("容器参数L: " + L2);
System.out.println("最小总费用: " + result2);
// 测试3：滑动窗口最小值
System.out.println("\n--- 测试3：滑动窗口最小值 ---");
long[] arr3 = {1, 3, -1, -3, 5, 3, 6, 7};
int k3 = 3;
long[] min3 = slidingWindowMin(arr3, k3);
System.out.println("数组: " + Arrays.toString(arr3));
System.out.println("窗口大小: " + k3);
System.out.println("窗口最小值: " + Arrays.toString(min3));
// 测试4：凸包查询
System.out.println("\n--- 测试4：凸壳直线查询 ---");
ConvexHullTrick cht = new ConvexHullTrick();
// 添加斜率递减的直线
cht.addLine(0, 0); // y = 0
cht.addLine(-1, 5); // y = -x + 5
cht.addLine(-2, 12); // y = -2x + 12
cht.addLine(-3, 20); // y = -3x + 20
System.out.println("添加直线: y=0, y=-x+5, y=-2x+12, y=-3x+20");
for (long x = 0; x <= 10; x++) {
System.out.printf("x=%d: min=%d%n", x, cht.queryMinBinary(x));
}
// 测试5：大规模性能测试
System.out.println("\n--- 测试5：性能对比 ---");
int n = 100000;
long[] t5 = new long[n];
long[] f5 = new long[n];
Random rand = new Random(42);
for (int i = 0; i < n; i++) {
t5[i] = rand.nextInt(100) + 1;
f5[i] = rand.nextInt(100) + 1;
}
long start = System.currentTimeMillis();
long fastResult = solveBatchScheduling(t5, f5, 1000);
long fastTime = System.currentTimeMillis() - start;
System.out.println("规模: n=" + n);
System.out.println("斜率优化结果: " + fastResult);
System.out.println("斜率优化耗时: " + fastTime + "ms");
System.out.println("复杂度: O(n) vs 朴素O(n²)的约" + (n * n / 1000 / Math.max(fastTime, 1)) + "倍加速");
}
}
凸包技巧变种
李超线段树（动态开点）
当斜率不单调时，需要用李超线段树维护，支持O(log² n)插入和查询。
/**
* 李超线段树：支持任意顺序插入直线，O(log² C)查询
* 适用于斜率不单调的场景
*/
class LiChaoTree {
static class Node {
Line line;
Node left, right;
}
Node root;
long xLeft, xRight; // 定义域范围
// 在区间[l,r]中，比较两条直线的优劣，保留更优者，下放次优者
void insert(Node node, long l, long r, Line newLine) {
long mid = (l + r) >> 1;
if (node.line == null) {
node.line = newLine;
return;
}
// 在mid处比较，保留更优的，将次优的传递到子树
if (newLine.eval(mid) < node.line.eval(mid)) {
Line tmp = node.line;
node.line = newLine;
newLine = tmp;
}
if (l == r) return;
if (newLine.eval(l) < node.line.eval(l)) {
if (node.left == null) node.left = new Node();
insert(node.left, l, mid, newLine);
} else if (newLine.eval(r) < node.line.eval(r)) {
if (node.right == null) node.right = new Node();
insert(node.right, mid + 1, r, newLine);
}
}
}
复杂度分析
| 场景 | 预处理 | 每次转移 | 总复杂度 | 适用条件 |
|---|---|---|---|---|
| 朴素DP | – | O(n) | O(n²) | 通用 |
| 单调队列优化 | – | O(1) | O(n) | 斜率、查询点均单调 |
| 二分凸壳 | O(n) | O(log n) | O(n log n) | 仅斜率单调 |
| 李超树 | O(log² C) | O(log² C) | O(n log² C) | 无单调性要求 |
判断可斜率优化的条件
一个DP转移可被斜率优化需满足：
1. 转移方程可写成 dp[i] = min/max { k[j] * x[i] + b[j] } + const[i]
2. 斜率k[j]具有单调性（或可排序）
3. 查询点x[i]具有单调性（或可用二分/线段树）
应用场景
- 生产调度：任务分批处理的最优费用
- 资源分配：预算约束下的项目选择
- 路径规划：带权图中的最优分段
- 字符串处理：最优分割与编码
- 金融建模：投资组合的动态优化
总结
斜率优化DP通过将代数问题几何化，利用凸壳的单调性质实现了动态规划的高效转移。其核心在于识别可分离的线性结构，并选择合适的凸壳维护策略。掌握从单调队列到李超线段树的完整技术栈，是处理大规模优化DP问题的关键能力。
