DP tối ưu hóa (Optimization DP)

Wiki › Thuật toán › Quy hoạch động (DP)

huunguyen · Last updated 7, Tháng 4, 2026, 21:36

Nhiều bài DP có công thức chuyển dạng:

d p [i] = {min}_{j < i} (d p [j] + cost (j, i))

Duyệt trâu tất cả $j$ cho mỗi $i$ cho độ phức tạp $O (N^{2})$ . Các kỹ thuật dưới đây giúp tối ưu xuống $O (N \log N)$ hoặc $O (N)$ khi cost có cấu trúc đặc biệt.

1. Convex Hull Trick (CHT)

Khi nào áp dụng?

Công thức chuyển có dạng:

d p [i] = {min}_{j < i} (d p [j] + b [j] \cdot a [i])

Mỗi trạng thái $j$ tương ứng với một đường thẳng $f_{j} (x) = b [j] \cdot x + d p [j]$ .

Bài toán trở thành: với mỗi $i$ , tìm đường thẳng cho giá trị nhỏ nhất tại $x = a [i]$ .

Ý tưởng

Tập các đường thẳng tối ưu tạo thành một bao lồi dưới (lower convex hull). Chỉ cần giữ các đường thẳng nằm trên bao lồi này.

Cài đặt — Stack đơn điệu (khi $a [i]$ và $b [j]$ đơn điệu)

#include <bits/stdc++.h>
using namespace std;

struct Line {
    long long m, b;
    long long eval(long long x) { return m * x + b; }
};

// Kiểm tra đường thẳng mid có cần thiết không
bool bad(Line l1, Line l2, Line l3) {
    // l2 bị l1, l3 "che" hoàn toàn
    return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
         <= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}

struct CHT {
    vector<Line> hull;
    int ptr = 0;

    void addLine(long long m, long long b) {
        Line l = {m, b};
        while (hull.size() >= 2 && bad(hull[hull.size()-2], hull[hull.size()-1], l))
            hull.pop_back();
        hull.push_back(l);
    }

    // Query khi x tăng dần (monotone queries)
    long long query(long long x) {
        while (ptr + 1 < (int)hull.size() && hull[ptr+1].eval(x) <= hull[ptr].eval(x))
            ptr++;
        return hull[ptr].eval(x);
    }
};

Độ phức tạp: $O (N)$ khi cả $b [j]$ (slope) và $a [i]$ (query) đều đơn điệu.

Cài đặt — Li Chao Tree (query bất kỳ)

struct LiChaoTree {
    static const int MAXV = 1e6 + 5;
    struct Line { long long m, b; long long eval(long long x) { return m*x+b; } };
    Line tree[4 * MAXV];
    bool has[4 * MAXV];

    void addLine(Line newLine, int node, int lo, int hi) {
        if (lo == hi) {
            if (!has[node] || newLine.eval(lo) < tree[node].eval(lo)) {
                tree[node] = newLine; has[node] = true;
            }
            return;
        }
        int mid = (lo + hi) / 2;
        bool leftBetter = newLine.eval(lo) < tree[node].eval(lo);
        bool midBetter  = newLine.eval(mid) < tree[node].eval(mid);
        if (midBetter) swap(tree[node], newLine), has[node] = true;
        if (lo == hi) return;
        if (leftBetter != midBetter) addLine(newLine, 2*node, lo, mid);
        else addLine(newLine, 2*node+1, mid+1, hi);
    }

    long long query(int x, int node, int lo, int hi) {
        long long res = has[node] ? tree[node].eval(x) : LLONG_MAX;
        if (lo == hi) return res;
        int mid = (lo + hi) / 2;
        if (x <= mid) return min(res, query(x, 2*node, lo, mid));
        else return min(res, query(x, 2*node+1, mid+1, hi));
    }
};

Độ phức tạp: $O (N \log V)$ với $V$ là khoảng giá trị query.

Ví dụ: Bài toán chia nhóm

n

học sinh có điểm

a [i]

. Chi phí tạo một nhóm từ

l

đến

r

là

(a [r] - a [l])^{2} + C

. Chia tất cả học sinh thành các nhóm liên tiếp với tổng chi phí nhỏ nhất.

// dp[i] = chi phí nhỏ nhất chia i học sinh đầu
// dp[i] = min_{j<i} (dp[j] + (a[i]-a[j+1])^2 + C)
// Khai triển: dp[j] + a[i]^2 - 2*a[i]*a[j+1] + a[j+1]^2 + C
// => đường thẳng: slope = -2*a[j+1], intercept = dp[j] + a[j+1]^2 + C

CHT cht;
dp[0] = 0;
cht.addLine(-2 * a[1], dp[0] + a[1]*a[1] + C);

for (int i = 1; i <= n; i++) {
    dp[i] = cht.query(a[i]) + a[i]*a[i];
    cht.addLine(-2 * a[i+1], dp[i] + a[i+1]*a[i+1] + C);
}

## 2. Divide & Conquer DP (D&C DP) ### Khi nào áp dụng? Công thức chuyển:

d p [i] [j] = {min}_{k \leq j} (d p [i - 1] [k] + cost (k, j))

Với điều kiện cost thỏa mãn bất đẳng thức tứ giác (quadrangle inequality), khi đó $opt [j]$ (vị trí $k$ tối ưu cho $j$ ) đơn điệu: $opt [j] \leq opt [j + 1]$ .

Thuật toán

Dùng chia để trị: tính $d p [i] [m i d]$ trước, sau đó giới hạn tìm kiếm $k$ cho nửa trái và nửa phải.

// dp[cur][j] = min cost, layer cur, position j
// opt[j] = vị trí k tối ưu cho j
long long dp[2][MAXN];
// cost(l, r): chi phí chuyển từ l sang r (cần tính trước hoặc O(1))

void solve(int layer, int lo, int hi, int optLo, int optHi) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    long long best = LLONG_MAX;
    int opt = optLo;

    for (int k = optLo; k <= min(mid, optHi); k++) {
        long long val = dp[layer ^ 1][k] + cost(k, mid);
        if (val < best) {
            best = val;
            opt = k;
        }
    }
    dp[layer][mid] = best;

    solve(layer, lo, mid - 1, optLo, opt);
    solve(layer, mid + 1, hi, opt, optHi);
}

// Gọi cho mỗi layer i:
// solve(i & 1, 0, n-1, 0, n-1);

Độ phức tạp: $O (N \log N)$ mỗi layer, $O (K N \log N)$ tổng ( $K$ layer).

3. Knuth's Optimization

Khi nào áp dụng?

DP khoảng dạng:

d p [l] [r] = {min}_{l \leq k < r} (d p [l] [k] + d p [k + 1] [r]) + w [l] [r]

Với $w [l] [r]$ thỏa mãn:

Monotone: $w [l] [r] \leq w [l^{'}] [r^{'}]$ với $l^{'} \leq l \leq r \leq r^{'}$ .
Quadrangle inequality: $w [a] [c] + w [b] [d] \leq w [a] [d] + w [b] [c]$ với $a \leq b \leq c \leq d$ .

Khi đó $opt [l] [r]$ (điểm chia tối ưu) thỏa: $opt [l] [r - 1] \leq opt [l] [r] \leq opt [l + 1] [r]$ .

Cài đặt

int opt[MAXN][MAXN];
long long dp[MAXN][MAXN];

// Khởi tạo
for (int i = 0; i < n; i++) {
    dp[i][i] = 0;
    opt[i][i] = i;
}

for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        dp[l][r] = LLONG_MAX;
        // Chỉ tìm k trong [opt[l][r-1], opt[l+1][r]]
        int lo = opt[l][r-1];
        int hi = (l + 1 <= r) ? opt[l+1][r] : r - 1;
        for (int k = lo; k <= min(hi, r - 1); k++) {
            long long val = dp[l][k] + dp[k+1][r] + w[l][r];
            if (val < dp[l][r]) {
                dp[l][r] = val;
                opt[l][r] = k;
            }
        }
    }
}

Độ phức tạp: $O (N^{2})$ thay vì $O (N^{3})$ .

Ví dụ áp dụng: Optimal BST, Stone merging (gộp đá), Hu-Shing algorithm.

Tổng kết

Kỹ thuật	Điều kiện	Từ	Xuống
Convex Hull Trick	`cost(j,i) = b[j]·a[i]`	$O (N^{2})$	$O (N)$ hoặc $O (N \log N)$
D&C DP	`opt[j]` đơn điệu	$O (N^{2})$	$O (N \log N)$
Knuth's Opt	$w$ thỏa QI	$O (N^{3})$	$O (N^{2})$

Quy tắc nhận dạng nhanh:

Có nhân $b [j] \cdot a [i]$ ? → CHT
DP layer và opt đơn điệu? → D&C DP
DP khoảng với $w$ thỏa QI? → Knuth

Bình luận

Không có bình luận tại thời điểm này.