DP Optimization

เทคนิค Optimization สำหรับ Dynamic Programming

DP Optimization

1. Divide and Conquer Optimization

เงื่อนไขการใช้งาน

เมื่อ DP มีรูปแบบ:

$dp[i][j] = \min_{k < j} (dp[i-1][k] + C(k, j))$

และ $opt[i][j] \leq opt[i][j+1]$ (optimal $k$ เพิ่มขึ้นเมื่อ $j$ เพิ่ม)

Implementation

void solve(int i, int jl, int jr, int kl, int kr) {
    if (jl > jr) return;
    
    int jm = (jl + jr) / 2;
    int bestK = kl;
    dp[i][jm] = LLONG_MAX;
    
    for (int k = kl; k <= min(kr, jm - 1); k++) {
        long long val = dp[i-1][k] + cost(k, jm);
        if (val < dp[i][jm]) {
            dp[i][jm] = val;
            bestK = k;
        }
    }
    
    solve(i, jl, jm - 1, kl, bestK);
    solve(i, jm + 1, jr, bestK, kr);
}

Time Complexity: $O(kn \log n)$ แทนที่จะเป็น $O(kn^2)$

2. Knuth’s Optimization

เงื่อนไขการใช้งาน

เมื่อ DP มีรูปแบบ:

$dp[i][j] = \min_{i < k < j} (dp[i][k] + dp[k][j]) + C(i, j)$

และ:

$C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ สำหรับ $a \leq b \leq c \leq d$ (quadrangle inequality)
$C(b, c) \leq C(a, d)$ สำหรับ $a \leq b \leq c \leq d$ (monotonicity)

Implementation

void knuth() {
    // opt[i][j] = optimal k for dp[i][j]
    vector<vector<int>> opt(n, vector<int>(n));
    
    // Base case
    for (int i = 0; i < n; i++) {
        dp[i][i] = 0;
        opt[i][i] = i;
    }
    
    // Fill by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MAX;
            
            // Only search in [opt[i][j-1], opt[i+1][j]]
            for (int k = opt[i][j-1]; k <= opt[i+1][j]; k++) {
                long long val = dp[i][k] + dp[k][j] + cost(i, j);
                if (val < dp[i][j]) {
                    dp[i][j] = val;
                    opt[i][j] = k;
                }
            }
        }
    }
}

Time Complexity: $O(n^2)$ แทนที่จะเป็น $O(n^3)$

3. Convex Hull Trick (CHT)

เงื่อนไขการใช้งาน

เมื่อ DP มีรูปแบบ:

$dp[i] = \min_{j < i} (dp[j] + b[j] \cdot a[i])$

โดยที่ $b[j]$ monotonically decreasing (หรือ increasing)

Implementation (Deque)

struct Line {
    long long m, c;  // y = mx + c
    long long eval(long long x) { return m * x + c; }
};

bool bad(Line l1, Line l2, Line l3) {
    // Check if l2 is useless
    return (l3.c - l1.c) * (l1.m - l2.m) <= (l2.c - l1.c) * (l1.m - l3.m);
}

class CHT {
    deque<Line> hull;
    
public:
    // Add line with decreasing slope
    void addLine(long long m, long long c) {
        Line l = {m, c};
        while (hull.size() >= 2 && bad(hull[hull.size()-2], hull[hull.size()-1], l)) {
            hull.pop_back();
        }
        hull.push_back(l);
    }
    
    // Query minimum at x (x increasing)
    long long query(long long x) {
        while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) {
            hull.pop_front();
        }
        return hull[0].eval(x);
    }
};

Li Chao Tree (General Case)

struct LiChaoTree {
    struct Line {
        long long m, c;
        long long eval(long long x) { return m * x + c; }
    };
    
    vector<Line> tree;
    int lo, hi;
    
    LiChaoTree(int lo, int hi) : lo(lo), hi(hi), tree(4 * (hi - lo + 1), {0, LLONG_MAX}) {}
    
    void addLine(int node, int l, int r, Line line) {
        int mid = (l + r) / 2;
        bool leftBetter = line.eval(l) < tree[node].eval(l);
        bool midBetter = line.eval(mid) < tree[node].eval(mid);
        
        if (midBetter) swap(tree[node], line);
        
        if (r - l == 1) return;
        
        if (leftBetter != midBetter) {
            addLine(2*node, l, mid, line);
        } else {
            addLine(2*node+1, mid, r, line);
        }
    }
    
    long long query(int node, int l, int r, long long x) {
        if (r - l == 1) return tree[node].eval(x);
        
        int mid = (l + r) / 2;
        if (x < mid) {
            return min(tree[node].eval(x), query(2*node, l, mid, x));
        } else {
            return min(tree[node].eval(x), query(2*node+1, mid, r, x));
        }
    }
    
    void addLine(long long m, long long c) {
        addLine(1, lo, hi, {m, c});
    }
    
    long long query(long long x) {
        return query(1, lo, hi, x);
    }
};

4. Slope Trick

ใช้สำหรับ

ปัญหาที่ cost function เป็น piecewise linear convex function

แนวคิด

เก็บ function ด้วย:

Minimum value
Slopes ทางซ้ายและขวาของ minimum

class SlopeTrick {
    long long minVal;
    priority_queue<long long> L;  // max-heap for left
    priority_queue<long long, vector<long long>, greater<>> R;  // min-heap for right
    
public:
    SlopeTrick() : minVal(0) {
        L.push(LLONG_MIN);
        R.push(LLONG_MAX);
    }
    
    // Add |x - a|
    void addAbs(long long a) {
        long long l = L.top(), r = R.top();
        
        if (a <= l) {
            minVal += l - a;
            L.pop();
            L.push(a);
            L.push(a);
            R.push(L.top());
            L.pop();
        } else if (a >= r) {
            minVal += a - r;
            R.pop();
            R.push(a);
            R.push(a);
            L.push(R.top());
            R.pop();
        } else {
            L.push(a);
            R.push(a);
        }
    }
    
    long long getMin() { return minVal; }
};

5. Aliens Trick (WQS Binary Search)

ใช้สำหรับ

เปลี่ยนปัญหา “เลือก exactly $k$ items” เป็น “เลือกจำนวนใดก็ได้ แต่แต่ละ item มี penalty $\lambda$ “

pair<long long, int> solve(long long penalty) {
    // Solve DP with penalty
    // Return (total cost with penalty, number of items chosen)
}

long long aliensOptimization(int n, int k) {
    long long lo = 0, hi = 1e18;
    
    while (hi - lo > 1) {
        long long mid = (lo + hi) / 2;
        auto [cost, cnt] = solve(mid);
        
        if (cnt >= k) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    
    auto [cost, cnt] = solve(lo);
    return cost - lo * k;
}

Summary

Technique	Condition	Original	Optimized
D&C	$opt$ monotonic	$O(kn^2)$	$O(kn \log n)$
Knuth	Quadrangle inequality	$O(n^3)$	$O(n^2)$
CHT	Linear cost	$O(n^2)$	$O(n)$ or $O(n \log n)$
Slope Trick	Piecewise linear	Varies	Efficient
Aliens	Choose exactly k	Hard	Binary search