Wiki › Thuật toán › Quy hoạch động (DP) › DP tối ưu hóa (Optimization DP)

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

huunguyen Updated Tháng sáu 1, 2026

Nhiều bài quy hoạch động (QHĐ) có công thức chuyển dạng

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

hoặc QHĐ khoảng dạng $d p [l] [r] = {min}_{k} (d p [l] [k] + d p [k + 1] [r]) + w [l] [r]$ . Cài đặt ngây thơ duyệt mọi $j$ (hoặc mọi điểm chia $k$ ) cho mỗi trạng thái, dẫn tới $O (N^{2})$ hoặc $O (N^{3})$ . Các kỹ thuật trong trang này khai thác cấu trúc đặc biệt của hàm cost để cắt bớt phần lớn các lựa chọn vô ích, đưa độ phức tạp xuống $O (N \log N)$ , $O (N)$ hoặc $O (N^{2})$ .

Ba kỹ thuật chính:

Kỹ thuật	Áp dụng khi	Giảm từ	Xuống
Convex Hull Trick (CHT)	$cost = b [j] \cdot a [i]$ (chuyển tuyến tính)	$O (N^{2})$	$O (N)$ / $O (N \log N)$
Divide & Conquer DP	điểm tối ưu $opt [j]$ đơn điệu	$O (K N^{2})$	$O (K N \log N)$
Knuth's Optimization	QHĐ khoảng, $w$ thỏa bất đẳng thức tứ giác	$O (N^{3})$	$O (N^{2})$

Ý tưởng / Trực giác

Vì sao việc duyệt trâu lại lãng phí? Trong cả ba trường hợp, khi $i$ (hoặc $r$ ) tăng, vị trí tối ưu $j$ (hoặc điểm chia $k$ ) không nhảy lung tung mà thay đổi một cách có quy luật. Nếu ta chứng minh được quy luật đó, ta không cần xét lại toàn bộ ứng viên ở mỗi bước.

1. Convex Hull Trick — mỗi trạng thái là một đường thẳng. Viết lại $d p [j] + b [j] \cdot a [i]$ thành $f_{j} (x) = b [j] \cdot x + d p [j]$ với $x = a [i]$ . Đây là một đường thẳng với hệ số góc $b [j]$ và tung độ gốc $d p [j]$ . Với mỗi truy vấn $x$ , ta cần đường thẳng cho giá trị nhỏ nhất tại $x$ . Khi vẽ tất cả đường thẳng lên mặt phẳng, đường bao dưới (lower envelope) của chúng là một đường gấp khúc lồi: tại mỗi $x$ chỉ có đúng một đoạn (một đường thẳng) là tối ưu. Một đường thẳng bị "che" hoàn toàn bởi hai đường khác thì không bao giờ tối ưu — ta loại nó vĩnh viễn. Nhờ đó tập đường thẳng cần giữ luôn tạo thành bao lồi, thêm/truy vấn rất nhanh.

2. D&C DP — tính đơn điệu của điểm tối ưu. Gọi $opt [j]$ là vị trí $k$ làm $d p [layer] [j]$ nhỏ nhất. Nếu hàm cost thỏa bất đẳng thức tứ giác (quadrangle inequality), người ta chứng minh được $opt [j] \leq opt [j + 1]$ : điểm tối ưu không bao giờ lùi khi $j$ tăng. Trực giác: nếu một điểm chia tốt cho vị trí $j$ thì với vị trí $j$ lớn hơn, điểm chia tốt cũng phải dịch sang phải (hoặc đứng yên), không thể tụt về trái. Khi đã biết tính đơn điệu này, ta tính $d p$ theo kiểu chia để trị: tính $d p [m i d]$ trước bằng cách quét toàn dải $[o p t L o, o p t H i]$ , rồi $opt [m i d]$ thu được sẽ chặn dải tìm kiếm cho hai nửa trái/phải.

3. Knuth — đơn điệu hai chiều cho QHĐ khoảng. Cũng từ bất đẳng thức tứ giác (và tính đơn điệu của $w$ ), điểm chia tối ưu $opt [l] [r]$ bị kẹp: $opt [l] [r - 1] \leq opt [l] [r] \leq opt [l + 1] [r] .$ Thay vì thử cả $r - l$ điểm chia cho mỗi khoảng $[l, r]$ , ta chỉ thử trong đoạn nhỏ giữa hai mốc trên. Tổng số phép thử trên mọi khoảng cùng độ dài co lại thành tổng nuốt chuỗi (telescoping), cho $O (N^{2})$ thay vì $O (N^{3})$ .

Ví dụ chạy tay (Convex Hull Trick)

Bài toán: chia $n$ giá trị đã sắp xếp thành các nhóm liên tiếp, chi phí một nhóm $[l, r]$ là $(a_{r} - a_{l})^{2} + C$ , cực tiểu tổng. Lấy $a = [1, 3, 4, 8]$ (1-indexed), $C = 5$ .

Công thức: $d p [i] = {min}_{j < i} (d p [j] + (a_{i} - a_{j + 1})^{2} + C)$ . Khai triển: $d p [i] = a_{i}^{2} + C + {min}_{j < i} (\underset{slope m}{\underset{⏟}{- 2 a_{j + 1}}} \cdot a_{i} + \underset{intercept b}{\underset{⏟}{d p [j] + a_{j + 1}^{2}}}) .$ Mỗi $j$ sinh đường thẳng $f_{j} (x) = m_{j} x + b_{j}$ , truy vấn tại $x = a_{i}$ .

Khởi tạo $d p [0] = 0$ . Thêm đường từ $j = 0$ : $m_{0} = - 2 a_{1} = - 2$ , $b_{0} = 0 + a_{1}^{2} = 1$ .

Bao dưới (lower envelope) các đường thẳng — chỉ giữ phần thấp nhất:

   giá trị f(x)
     |   \         . đường j=0: f0(x) = -2x + 1
     |    \      .
     |     \   .
     |      \.        <- giao điểm: đổi đường tối ưu
     |      .\
     |    .   \
     +----------------> x = a[i]
          ^truy vấn x=a[i]

Tính từng bước (ô [DP] là giá trị đang điền):

$i$	$x = a_{i}$	đường tối ưu tại $x$	$d p [i] = a_{i}^{2} + C + (min)$
1	3	$f_{0} (3) = - 6 + 1 = - 5$	$9 + 5 - 5 =$ [9]
2	4	xét $f_{0}, f_{1}$	$16 + 5 + min =$ [?]
3	8	xét cả ba đường	…

Sau khi tính $d p [1] = 9$ , thêm đường $j = 1$ : $m_{1} = - 2 a_{2} = - 6$ , $b_{1} = d p [1] + a_{2}^{2} = 9 + 9 = 18$ .

Tại $i = 2$ , $x = 4$ : $f_{0} (4) = - 8 + 1 = - 7$ ; $f_{1} (4) = - 24 + 18 = - 6$ . Nhỏ hơn là $f_{0} (4) = - 7$ (đường $j = 0$ vẫn tối ưu ở $x = 4$ ). $d p [2] = 16 + 5 + (- 7) = 14 .$

Thêm đường $j = 2$ : $m_{2} = - 2 a_{3} = - 8$ , $b_{2} = d p [2] + a_{3}^{2} = 14 + 16 = 30$ . Lúc thêm, kiểm tra đường giữa có bị che không bằng hàm bad(...); nếu có thì pop.

Tại $i = 3$ , $x = 8$ : $f_{0} (8) = - 15$ , $f_{1} (8) = - 30$ , $f_{2} (8) = - 34$ . Nhỏ nhất $f_{2} (8) = - 34$ . $d p [3] = 64 + 5 + (- 34) = 35 .$

Đáp số $d p [4]$ tính tương tự. Điểm mấu chốt: ở mỗi truy vấn ta không quét lại mọi $j$ — con trỏ trên bao lồi chỉ tiến, nên tổng chi phí truy vấn là $O (N)$ .

Cài đặt

1. Convex Hull Trick — stack đơn điệu (slope và query đều đơn điệu)

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

struct Line {
    ll m, b;                       // f(x) = m*x + b
    ll eval(ll x) const { return m * x + b; }
};

// True nếu l2 bị l1 & l3 che hoàn toàn => l2 vô dụng, loại bỏ.
// Dùng __int128 để tránh tràn khi nhân hai hiệu lớn.
bool bad(const Line& l1, const Line& l2, const Line& l3) {
    return (__int128)(l3.b - l1.b) * (l1.m - l2.m)
        <= (__int128)(l2.b - l1.b) * (l1.m - l3.m);
}

struct CHT {                       // dùng cho bài tối THIỂU, slope giảm dần
    vector<Line> hull;
    int ptr = 0;                   // con trỏ truy vấn, chỉ tiến

    void addLine(ll m, ll b) {
        Line l = {m, b};
        // Bỏ các đường ở đỉnh stack đã bị che bởi đường mới
        while (hull.size() >= 2 &&
               bad(hull[hull.size()-2], hull.back(), l))
            hull.pop_back();
        hull.push_back(l);
    }

    // Yêu cầu: x tăng dần qua các lần gọi -> con trỏ chỉ tiến tới
    ll query(ll x) {
        if (ptr >= (int)hull.size()) ptr = (int)hull.size() - 1;
        while (ptr + 1 < (int)hull.size() &&
               hull[ptr+1].eval(x) <= hull[ptr].eval(x))
            ptr++;
        return hull[ptr].eval(x);
    }
};

Khi truy vấn không đơn điệu, thay query tuyến tính bằng tìm kiếm nhị phân trên bao lồi, hoặc dùng Li Chao Tree (truy vấn $x$ bất kỳ, $O (\log V)$ mỗi thao tác):

struct LiChao {
    struct Line { ll m, b; ll eval(ll x){ return m*x + b; } };
    int n; vector<Line> tr; vector<char> has;
    LiChao(int sz): n(sz), tr(4*sz), has(4*sz, 0) {}

    void add(Line nw, int node, int lo, int hi) {
        int mid = (lo + hi) >> 1;
        bool lBet = !has[node] || nw.eval(lo)  < tr[node].eval(lo);
        bool mBet = !has[node] || nw.eval(mid) < tr[node].eval(mid);
        if (mBet) { swap(tr[node], nw); has[node] = 1; }   // đường tốt hơn ở giữa thì giữ lại
        if (lo == hi) return;
        // Đường thua ở giữa chỉ có thể tốt hơn ở MỘT nửa -> đệ quy 1 nhánh
        if (lBet != mBet) add(nw, 2*node,   lo,   mid);
        else              add(nw, 2*node+1, mid+1, hi);
    }
    ll query(int x, int node, int lo, int hi) {
        ll res = has[node] ? tr[node].eval(x) : LLONG_MAX;
        if (lo == hi) return res;
        int mid = (lo + hi) >> 1;
        if (x <= mid) return min(res, query(x, 2*node,   lo,   mid));
        else          return min(res, query(x, 2*node+1, mid+1, hi));
    }
};

2. Divide & Conquer DP

const int MAXN = 1e5 + 5;
ll dp_prev[MAXN], dp_cur[MAXN];   // hai layer luân phiên để tiết kiệm bộ nhớ
ll cost(int l, int r);            // chi phí đoạn [l..r], cần tính O(1) (vd prefix sum)

// Tính dp_cur[lo..hi], biết opt nằm trong [optLo..optHi]
void solve(int lo, int hi, int optLo, int optHi) {
    if (lo > hi) return;
    int mid = (lo + hi) >> 1;
    ll best = LLONG_MAX; int opt = optLo;
    // Quét tìm điểm chia tối ưu cho mid (đây là chỗ tốn công duy nhất)
    for (int k = optLo; k <= min(mid, optHi); k++) {
        ll val = dp_prev[k] + cost(k + 1, mid);
        if (val < best) { best = val; opt = k; }
    }
    dp_cur[mid] = best;
    // Tính đơn điệu: opt của nửa trái <= opt[mid] <= opt của nửa phải
    solve(lo, mid - 1, optLo, opt);
    solve(mid + 1, hi, opt, optHi);
}
// Mỗi layer: swap(dp_prev, dp_cur); solve(1, n, 0, n);

3. Knuth's Optimization

int opt[MAXN][MAXN];
ll dp[MAXN][MAXN], w[MAXN][MAXN];   // w[l][r]: trọng số khoảng [l..r]

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Ỉ duyệt k trong [opt[l][r-1], opt[l+1][r]] -> tổng O(N^2)
        for (int k = opt[l][r-1]; k <= opt[l+1][r]; k++) {
            ll val = dp[l][k] + dp[k+1][r] + w[l][r];
            if (val < dp[l][r]) { dp[l][r] = val; opt[l][r] = k; }
        }
    }
// Đáp số: dp[0][n-1]

Độ phức tạp

Kỹ thuật	Thời gian	Bộ nhớ	Vì sao
CHT (stack đơn điệu)	$O (N)$	$O (N)$	Mỗi đường thêm/loại đúng 1 lần; con trỏ truy vấn chỉ tiến, tổng $\leq N$ bước.
CHT (Li Chao Tree)	$O (N \log V)$	$O (N + V)$	Mỗi `add`/`query` đi từ gốc xuống lá của cây phủ miền giá trị $V$ , sâu $\log V$ .
D&C DP	$O (K N \log N)$	$O (N)$	Mỗi mức đệ quy có tổng dải tìm kiếm $O (N)$ ; sâu $O (\log N)$ mức; nhân $K$ layer. Chỉ lưu 2 layer nên bộ nhớ $O (N)$ .
Knuth	$O (N^{2})$	$O (N^{2})$	Telescoping: tổng $\sum (o p t [l + 1] [r] - o p t [l] [r - 1])$ trên mọi khoảng cùng độ dài là $O (N)$ , có $N$ độ dài. Hai bảng $d p$ , $o p t$ kích thước $N^{2}$ .

Lưu ý bộ nhớ: D&C DP dùng kỹ thuật 2 layer luân phiên nên dù có $K$ tầng vẫn chỉ tốn $O (N)$ . Knuth bắt buộc bảng $N^{2}$ , nên thường chỉ chạy được với $N ≲ 5000$ .

⚠️ Lỗi thường gặp

Tràn số khi so sánh độ dốc (CHT). Hàm bad nhân hai hiệu lớn; với giá trị tới $10^{9}$ tích vượt long long. Phải dùng __int128 (hoặc so sánh bằng phép chia số thực có sai số). Triệu chứng: AC test nhỏ, WA test lớn không rõ lý do.
Áp dụng CHT stack khi điều kiện đơn điệu bị vi phạm. Phiên bản stack + con trỏ chỉ đúng khi slope đơn điệu lúc thêm và $x$ đơn điệu lúc truy vấn. Nếu một trong hai không đơn điệu mà vẫn dùng ptr++, con trỏ "trượt qua" đường tối ưu và không quay lại được. Khi đó phải tìm nhị phân hoặc dùng Li Chao Tree.
Nhầm min/max và chiều sắp xếp đường thẳng. CHT cho cực tiểu giữ bao dưới (slope giảm), cho cực đại giữ bao trên (slope tăng). Đảo nhầm chiều <=/>= trong bad/query cho kết quả sai âm thầm. Mẹo: với bài max, đổi dấu toàn bộ rồi giải bài min.
Off-by-one trong chỉ số đoạn (CHT/D&C). Công thức $(a_{i} - a_{j + 1})^{2}$ dùng $a_{j + 1}$ chứ không phải $a_{j}$ — đường thẳng phải thêm bằng $j + 1$ . Sai chỉ số làm lệch toàn bộ nghiệm. Kiểm tra bằng cách chạy tay $N = 2, 3$ .
D&C DP áp dụng khi opt không đơn điệu. Nếu hàm cost không thỏa bất đẳng thức tứ giác, tính đơn điệu của opt không còn đúng, và việc chặn dải $[o p t L o, o p t]$ , $[o p t, o p t H i]$ sẽ bỏ sót điểm tối ưu. Phải chứng minh (hoặc kiểm thử brute-force) tính đơn điệu trước khi tin tưởng.
Knuth: quên cập nhật opt[i][i] hoặc duyệt sai biên. Khởi tạo thiếu opt[i][i]=i khiến opt[l][r-1] đọc rác. Ngoài ra phải duyệt theo độ dài tăng dần (len từ 2 đến n) để opt[l][r-1] và opt[l+1][r] đã được tính trước.
Sai lầm về độ phức tạp Knuth. Nhìn vào hai vòng for lồng cộng vòng k dễ tưởng $O (N^{3})$ . Chỉ khi $k$ bị chặn bởi opt thì mới là $O (N^{2})$ — nếu vô tình duyệt k từ l đến r-1 thì mất hết lợi ích.

Biến thể / Mở rộng

CHT động (LineContainer): dùng std::multiset để chèn/xóa đường khi cả slope lẫn truy vấn đều không đơn điệu, $O (\log N)$ mỗi thao tác.
Lagrangian / Alien Trick: khi ràng buộc "chia đúng $K$ nhóm", phạt mỗi lần chia một hằng $λ$ rồi tìm nhị phân $λ$ — biến bài $K$ -layer thành 1-layer kết hợp được với CHT/D&C.
SMAWK: thuật toán nâng cao tính minimum hàng của ma trận Monge trong $O (N)$ , thay cho D&C $O (N \log N)$ .
Liên quan: xem thêm Quy hoạch động khoảng (nền tảng cho Knuth) và trang cha Quy hoạch động.

Bài tập luyện

Đội Hợp Xướng Hogwarts (choirform) — (Veteran) QHĐ trên lưới có tối ưu hóa chuyển trạng thái, làm quen ý tưởng cắt bớt ứng viên trước khi vào CHT thuần.
Nhà kính của Sprout (greenhouse) — (Expert) kết hợp Convex Hull Trick và chia để trị; bài "tất cả trong một" để luyện nhận dạng dạng chuyển tuyến tính.
Người Ăn Bánh (pieaters) — (Expert) Divide & Conquer DP điển hình: tận dụng tính đơn điệu của điểm tối ưu để giảm một bậc.
Chuồng Bò Tròn Mới (cbarnrev) — (Expert) D&C DP nhiều layer trên cấu trúc vòng, luyện kỹ thuật 2 layer luân phiên và chặn dải opt.
Chia Mảng Knuth (knuthdiv) — (Expert) áp dụng trực tiếp Knuth's Optimization cho bài chia mảng, kiểm chứng bất đẳng thức tứ giác.