Monotonic DP Optimization

Master convex hull trick, divide-and-conquer optimization, and other advanced DP acceleration methods

Overview

DP optimization techniques are key to solving large-scale dynamic programming problems. This chapter explores convex hull trick, divide-and-conquer optimization, quadrangle inequality, and other advanced methods to reduce DP complexity from O(n²) to O(n log n) or O(n).

Core Content

1. Convex Hull Trick Optimization

// Convex Hull Trick DP optimization
#include <iostream>
#include <vector>
#include <deque>
using namespace std;

struct Line {
    long long k, b;
    int id;
    
    Line(long long _k, long long _b, int _id) : k(_k), b(_b), id(_id) {}
    
    long long eval(long long x) {
        return k * x + b;
    }
};

class ConvexHullTrick {
private:
    deque<Line> lines;
    
    // Check if middle line should be removed
    bool bad(Line l1, Line l2, Line l3) {
        // Intersection comparison: (b2-b1)/(k1-k2) >= (b3-b2)/(k2-k3)
        return (l2.b - l1.b) * (l2.k - l3.k) >= (l3.b - l2.b) * (l1.k - l2.k);
    }
    
public:
    // Add line (decreasing slope)
    void addLine(long long k, long long b, int id) {
        Line newLine(k, b, id);
        
        // Maintain lower convex hull
        while (lines.size() >= 2 && bad(lines[lines.size()-2], lines[lines.size()-1], newLine)) {
            lines.pop_back();
        }
        lines.push_back(newLine);
    }
    
    // Query minimum (x monotonically increasing)
    pair<long long, int> queryMin(long long x) {
        // Remove lines that are no longer optimal
        while (lines.size() >= 2 && lines[0].eval(x) >= lines[1].eval(x)) {
            lines.pop_front();
        }
        
        return {lines[0].eval(x), lines[0].id};
    }
    
    void clear() {
        lines.clear();
    }
};

// Application: Minimum cost buying
long long minCostBuying(vector<long long>& cost, vector<long long>& amount) {
    int n = cost.size();
    vector<long long> dp(n + 1, LLONG_MAX);
    vector<long long> prefixSum(n + 1, 0);
    
    // Calculate prefix sum
    for (int i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + amount[i];
    }
    
    dp[0] = 0;
    ConvexHullTrick cht;
    cht.addLine(0, 0, 0);
    
    for (int i = 1; i <= n; i++) {
        auto [minVal, fromIdx] = cht.queryMin(prefixSum[i]);
        dp[i] = minVal + cost[i - 1] * prefixSum[i];
        
        // Add new transition line
        cht.addLine(-prefixSum[i], dp[i], i);
    }
    
    return dp[n];
}

// Application: Optimal factory placement
long long optimalFactoryPlacement(vector<long long>& positions, vector<long long>& demands) {
    int n = positions.size();
    vector<long long> dp(n, LLONG_MAX);
    
    ConvexHullTrick cht;
    
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i] = 0;
        } else {
            auto [minVal, fromIdx] = cht.queryMin(positions[i]);
            dp[i] = minVal;
        }
        
        // Add transition from current position
        long long slope = -demands[i];
        long long intercept = dp[i] + demands[i] * positions[i];
        cht.addLine(slope, intercept, i);
    }
    
    return dp[n - 1];
}

int main() {
    // Test minimum cost buying
    vector<long long> cost = {2, 3, 1, 4};
    vector<long long> amount = {1, 2, 3, 1};
    
    cout << "Minimum buying cost: " 
         << minCostBuying(cost, amount) << endl;
    
    // Test factory placement
    vector<long long> positions = {1, 3, 6, 8};
    vector<long long> demands = {2, 1, 3, 2};
    
    cout << "Optimal factory placement cost: " 
         << optimalFactoryPlacement(positions, demands) << endl;
    
    return 0;
}

2. Divide and Conquer Optimization

// Divide and conquer DP optimization
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class DivideConquerDP {
private:
    vector<vector<long long>> cost;
    vector<long long> dp, newDp;
    int n;
    
    // Calculate transition cost
    long long getCost(int i, int j) {
        if (i > j) return LLONG_MAX;
        return cost[i][j];
    }
    
    // Divide and conquer DP calculation
    void solve(int l, int r, int optL, int optR) {
        if (l > r) return;
        
        int mid = (l + r) / 2;
        int optMid = optL;
        long long bestCost = LLONG_MAX;
        
        // Find optimal transition point
        for (int k = optL; k <= min(mid - 1, optR); k++) {
            long long currentCost = dp[k] + getCost(k + 1, mid);
            if (currentCost < bestCost) {
                bestCost = currentCost;
                optMid = k;
            }
        }
        
        newDp[mid] = bestCost;
        
        // Recursively process left and right parts
        solve(l, mid - 1, optL, optMid);
        solve(mid + 1, r, optMid, optR);
    }
    
public:
    // Initialize
    DivideConquerDP(vector<vector<long long>>& costs) {
        cost = costs;
        n = cost.size();
        dp.resize(n);
        newDp.resize(n);
    }
    
    // Calculate optimal solution
    long long solve() {
        // Initial state
        for (int i = 0; i < n; i++) {
            dp[i] = getCost(0, i);
        }
        
        // Layer by layer calculation
        for (int layer = 1; layer < n; layer++) {
            fill(newDp.begin(), newDp.end(), LLONG_MAX);
            solve(0, n - 1, 0, n - 1);
            dp = newDp;
        }
        
        return dp[n - 1];
    }
};

// Application: Optimal bipartite matching
long long optimalMatching(vector<vector<long long>>& weights) {
    int n = weights.size();
    vector<vector<long long>> dp(n, vector<long long>(n, LLONG_MAX));
    
    // Preprocess interval costs
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long long sum = 0;
            for (int k = i; k <= j; k++) {
                sum += weights[k][k]; // Simplified cost calculation
            }
            dp[i][j] = sum;
        }
    }
    
    DivideConquerDP dcDP(dp);
    return dcDP.solve();
}

// Application: Optimized matrix chain multiplication
class OptimizedMatrixChain {
private:
    vector<int> dims;
    vector<vector<long long>> cost;
    int n;
    
    void precomputeCosts() {
        cost.assign(n, vector<long long>(n, 0));
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                cost[i][j] = LLONG_MAX;
                
                for (int k = i; k < j; k++) {
                    long long c = cost[i][k] + cost[k + 1][j] + 
                                 (long long)dims[i] * dims[k + 1] * dims[j + 1];
                    cost[i][j] = min(cost[i][j], c);
                }
            }
        }
    }
    
public:
    OptimizedMatrixChain(vector<int>& dimensions) {
        dims = dimensions;
        n = dims.size() - 1;
        precomputeCosts();
    }
    
    long long solve() {
        DivideConquerDP dcDP(cost);
        return dcDP.solve();
    }
};

int main() {
    // Test optimal matching
    vector<vector<long long>> weights = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    cout << "Optimal matching cost: " 
         << optimalMatching(weights) << endl;
    
    // Test matrix chain multiplication
    vector<int> dimensions = {40, 20, 30, 10, 30};
    OptimizedMatrixChain omc(dimensions);
    
    cout << "Optimized matrix chain cost: " 
         << omc.solve() << endl;
    
    return 0;
}

Problem-Solving Tips

🎯 Optimization Recognition

Recognize conditions for DP optimization: convex hull trick needs monotonicity, divide-and-conquer needs quadrangle inequality.

⚡ Complexity Analysis

Correctly analyze optimized complexity: convex hull trick O(n), divide-and-conquer O(n log n), choose appropriate optimization methods.

🔧 Implementation Details

Pay attention to numerical precision and boundary conditions, correctly maintain monotonic properties of data structures.

🧮 Application Scenarios

Suitable for large-scale DP problems: factory placement, resource allocation, path optimization, and other classic problems.