每日算法 — 使用java实现斜率优化：动态规划凸包优化与决策单调性

引言

斜率优化（Slope Optimization / Convex Hull Trick）是动态规划的高级优化技巧，适用于状态转移方程形如 dp[i] = min(dp[j] + cost(j, i)) 且 cost 函数满足特定单调性的问题。通过维护一个下凸壳（或上凸壳），将原本 O(n²) 的DP优化到 O(n log n) 甚至 O(n)。本文使用Java实现斜率优化的核心算法，并通过一个经典的运输成本问题展示其应用。

问题引入：运输成本优化

有 n 批货物依次排列，第 i 批货物重量为 w[i]，需要将货物分批运输。每批运输的代价为 (这批货物总重量 + 固定启动成本)²。求将所有货物运完的最小总代价。

形式化：设 dp[i] 为运完前 i 批货物的最小代价，sum[i] 为前缀重量和。

dp[i] = min(dp[j] + (sum[i] - sum[j] + C)²) for j < i

展开后：dp[i] = min(dp[j] + sum[j]² - 2*(sum[i]+C)*sum[j]) + (sum[i]+C)²

令 y_j = dp[j] + sum[j]², x_j = sum[j]，则对每个 j，在坐标系中是一条斜率为 2*(sum[i]+C) 的直线，求最小截距。这正是一个凸包问题。

算法原理

将每个决策点 j 看作平面上的点 (x_j, y_j)，其中：
– x_j = sum[j]
– y_j = dp[j] + sum[j]²

对于当前状态 i，需要找到使 y_j - 2*(sum[i]+C)*x_j 最小的点 j。这等价于用斜率为 2*(sum[i]+C) 的直线从下方去切这些点，切到的第一个点即为最优决策点。

由于斜率 2*(sum[i]+C) 单调递增，我们可以用单调队列维护下凸壳，实现均摊 O(1) 的查询。

Java实现

import java.util.*;

/**
 * 斜率优化动态规划：凸包优化实现
 * 问题：运输成本最小化
 */
public class SlopeOptimization {

    /**
     * 基础DP版本：时间复杂度 O(n²)
     */
    public static long minCostBasic(long[] w, long C) {
        int n = w.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + w[i - 1];
        }

        long[] dp = new long[n + 1];
        Arrays.fill(dp, Long.MAX_VALUE / 4);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                long cost = dp[j] + (sum[i] - sum[j] + C) * (sum[i] - sum[j] + C);
                dp[i] = Math.min(dp[i], cost);
            }
        }

        return dp[n];
    }

    /**
     * 斜率优化版本：时间复杂度 O(n)
     * 使用单调队列维护下凸壳
     */
    public static long minCostOptimized(long[] w, long C) {
        int n = w.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + w[i - 1];
        }

        long[] dp = new long[n + 1];
        dp[0] = 0;

        // 单调队列存储决策点下标 j
        // 维护下凸壳：相邻三点的斜率单调递增
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(0);

        for (int i = 1; i <= n; i++) {
            // 查询：找到最优决策点
            // 队首两个点 j1, j2，如果 slope(j1, j2) <= 2*(sum[i]+C)，则 j1 不再最优
            long currentSlope = 2 * (sum[i] + C);

            while (deque.size() >= 2) {
                int j1 = deque.peekFirst();
                int j2 = deque.peekFirst() == deque.getFirst() 
                    ? ((LinkedList<Integer>) deque).get(1) : -1;
                // 使用迭代器获取第二个元素
                Iterator<Integer> it = deque.iterator();
                j1 = it.next();
                j2 = it.next();

                if (slope(sum, dp, j1, j2) <= currentSlope) {
                    deque.pollFirst();
                } else {
                    break;
                }
            }

            int bestJ = deque.peekFirst();
            dp[i] = dp[bestJ] + (sum[i] - sum[bestJ] + C) * (sum[i] - sum[bestJ] + C);

            // 插入新决策点 i，维护下凸壳
            // 队尾三个点 j1, j2, i，如果 slope(j1,j2) >= slope(j2,i)，则 j2 在凸包内，弹出 j2
            while (deque.size() >= 2) {
                Iterator<Integer> it = deque.iterator();
                int[] last = new int[deque.size()];
                int idx = 0;
                while (it.hasNext()) last[idx++] = it.next();

                int j1 = last[last.length - 2];
                int j2 = last[last.length - 1];

                if (slope(sum, dp, j1, j2) >= slope(sum, dp, j2, i)) {
                    // 弹出队尾
                    deque.pollLast();
                } else {
                    break;
                }
            }
            deque.offerLast(i);
        }

        return dp[n];
    }

    /**
     * 计算两点之间的斜率：(y2 - y1) / (x2 - x1)
     * 使用交叉相乘避免浮点数精度问题
     */
    private static double slope(long[] sum, long[] dp, int j1, int j2) {
        long x1 = sum[j1];
        long y1 = dp[j1] + sum[j1] * sum[j1];
        long x2 = sum[j2];
        long y2 = dp[j2] + sum[j2] * sum[j2];

        if (x1 == x2) return y2 > y1 ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY;
        return (double) (y2 - y1) / (double) (x2 - x1);
    }

使用LinkedList的优化实现

    /**
     * 使用LinkedList的干净实现版本
     */
    public static long minCostClean(long[] w, long C) {
        int n = w.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + w[i - 1];
        }

        long[] dp = new long[n + 1];
        dp[0] = 0;

        // 使用LinkedList便于访问前两个/后两个元素
        LinkedList<Integer> q = new LinkedList<>();
        q.addLast(0);

        for (int i = 1; i <= n; i++) {
            long k = 2 * (sum[i] + C); // 当前查询斜率

            // 队首弹出非最优决策
            while (q.size() >= 2 && 
                   getSlope(sum, dp, q.get(0), q.get(1)) <= k) {
                q.pollFirst();
            }

            int j = q.getFirst();
            dp[i] = dp[j] + (sum[i] - sum[j] + C) * (sum[i] - sum[j] + C);

            // 队尾维护下凸壳
            while (q.size() >= 2 &&
                   getSlope(sum, dp, q.get(q.size() - 2), q.getLast()) >=
                   getSlope(sum, dp, q.getLast(), i)) {
                q.pollLast();
            }
            q.addLast(i);
        }

        return dp[n];
    }

    private static double getSlope(long[] sum, long[] dp, int i, int j) {
        long xi = sum[i], xj = sum[j];
        long yi = dp[i] + sum[i] * sum[i];
        long yj = dp[j] + sum[j] * sum[j];
        return (double)(yj - yi) / (double)(xj - xi);
    }

一般化模板

    /**
     * 斜率优化通用模板
     * 适用于：dp[i] = min/max(dp[j] + f(j, i))，其中最优决策点具有单调性
     * 
     * @param points 每个决策点的坐标 (x[j], y[j])，其中 y[j] 包含 dp[j]
     * @param querySlopes 每次查询的斜率，必须单调
     */
    public static long[] convexHullOptimization(long[][] points, double[] querySlopes) {
        int n = points.length;
        int q = querySlopes.length;
        long[] dp = new long[q];

        LinkedList<Integer> hull = new LinkedList<>();
        hull.addLast(0);

        for (int i = 0; i < q; i++) {
            double k = querySlopes[i];

            // 查询最优决策
            while (hull.size() >= 2 && 
                   slope(points, hull.get(0), hull.get(1)) <= k) {
                hull.pollFirst();
            }

            int best = hull.getFirst();
            // dp[i] = points[best][1] - k * points[best][0] + ... 根据具体公式计算

            // 插入新点（如果当前查询也产生新决策点）
            // while (hull.size() >= 2 && ...)
        }

        return dp;
    }

    private static double slope(long[][] points, int i, int j) {
        if (points[i][0] == points[j][0]) return Double.POSITIVE_INFINITY;
        return (double)(points[j][1] - points[i][1]) / (double)(points[j][0] - points[i][0]);
    }

二分查找版本（斜率非单调）

    /**
     * 当查询斜率不单调时，使用二分查找定位最优决策点
     * 时间复杂度 O(n log n)
     */
    public static long minCostBinarySearch(long[] w, long C, double[] customSlopes) {
        int n = w.length;
        long[] sum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + w[i - 1];
        }

        long[] dp = new long[n + 1];
        dp[0] = 0;

        // 用ArrayList存储凸包上的点，支持二分查找
        List<Integer> hull = new ArrayList<>();
        hull.add(0);

        for (int i = 1; i <= n; i++) {
            double k = customSlopes != null ? customSlopes[i] : 2 * (sum[i] + C);

            // 二分查找最优决策点
            int left = 0, right = hull.size() - 1;
            while (left < right) {
                int mid = (left + right) / 2;
                if (getSlope(sum, dp, hull.get(mid), hull.get(mid + 1)) <= k) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            int bestJ = hull.get(left);
            dp[i] = dp[bestJ] + (sum[i] - sum[bestJ] + C) * (sum[i] - sum[bestJ] + C);

            // 维护凸包（仍然需要保持斜率单调递增）
            while (hull.size() >= 2 &&
                   getSlope(sum, dp, hull.get(hull.size() - 2), hull.get(hull.size() - 1)) >=
                   getSlope(sum, dp, hull.get(hull.size() - 1), i)) {
                hull.remove(hull.size() - 1);
            }
            hull.add(i);
        }

        return dp[n];
    }

完整测试与对比

    public static void main(String[] args) {
        long[] w = {3, 5, 2, 7, 4, 6, 1, 8, 3, 5};
        long C = 10;

        System.out.println("=== 斜率优化动态规划 ===\n");
        System.out.println("货物重量: " + Arrays.toString(w));
        System.out.println("固定启动成本 C = " + C);
        System.out.println();

        long t1 = System.currentTimeMillis();
        long cost1 = minCostBasic(w, C);
        System.out.println("基础DP O(n²) 结果: " + cost1 + "，耗时: " + (System.currentTimeMillis() - t1) + "ms");

        t1 = System.currentTimeMillis();
        long cost2 = minCostClean(w, C);
        System.out.println("斜率优化 O(n) 结果: " + cost2 + "，耗时: " + (System.currentTimeMillis() - t1) + "ms");

        // 大规模测试
        System.out.println("\n大规模测试 (n=50000):");
        long[] largeW = new long[50000];
        Random rand = new Random(42);
        for (int i = 0; i < 50000; i++) {
            largeW[i] = rand.nextInt(100) + 1;
        }

        t1 = System.currentTimeMillis();
        long cost3 = minCostClean(largeW, C);
        System.out.println("斜率优化 O(n) 结果: " + cost3 + "，耗时: " + (System.currentTimeMillis() - t1) + "ms");
    }
}

复杂度分析

总结

本文通过运输成本问题引入斜率优化思想，将动态规划的复杂度从 O(n²) 优化到 O(n)。核心在于将决策点转化为平面上的点集，通过维护下凸壳实现快速查询最优决策。读者可以掌握凸包优化的数学原理与代码实现，并将其应用于具有决策单调性的DP问题中。