Thi đấu

Tối Ưu Quy Hoạch Động Chia Để Trị (Divide and Conquer DP)

Tối ưu quy hoạch động chia để trị (Divide and Conquer Optimization) tận dụng tính đơn điệu của điểm chuyển trạng thái tối ưu để giảm độ phức tạp bài toán phân hoạch K đoạn từ O(K * N^2) xuống O(K * N log N).

Tối Ưu Quy Hoạch Động Chia Để Trị (Divide and Conquer DP)

Trong các kỳ thi lập trình thi đấu đỉnh cao như VNOI, VOI và ICPC Regional, các bài toán phân hoạch dãy số thành nhiều đoạn con liên tiếp luôn là một chủ đề trọng tâm. Dạng tổng quát thường gặp nhất là:

Cho dãy số gồm \(N\) phần tử, cần chia dãy thành đúng \(K\) đoạn con liên tiếp sao cho tổng chi phí của các đoạn là nhỏ nhất (hoặc lớn nhất).

Công thức quy hoạch động tự nhiên cho bài toán này có dạng: Gọi \(dp[i][j]\) là chi phí tối ưu khi phân hoạch tiền tố gồm \(j\) phần tử đầu tiên (\(1 \le j \le N\)) thành đúng \(i\) đoạn (\(1 \le i \le K\)). Khi đó, chuyển trạng thái được xác định bằng cách duyệt vị trí bắt đầu của đoạn thứ \(i\):

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

Trong đó \(C(k + 1, j)\) là chi phí của đoạn con từ vị trí \(k + 1\) đến vị trí \(j\).

Nếu tính toán trực tiếp:

  • Có \(K\) tầng trạng thái (\(1 \le i \le K\)).
  • Mỗi tầng cần tính giá trị cho \(N\) vị trí \(j\).
  • Để tính mỗi \(dp[i][j]\), ta phải duyệt qua \(j\) điểm chuyển trạng thái \(k\). Tổng thời gian thực thi là \(O(K \cdot N^2)\). Khi \(N = 5 \cdot 10^4\) và \(K = 20\), số phép tính lên tới \(2.5 \cdot 10^{10}\), chắc chắn nhận kết quả Time Limit Exceeded (TLE).

Kỹ thuật Tối ưu quy hoạch động Chia để trị (Divide and Conquer DP Optimization) là chiếc chìa khóa vạn năng giúp phá vỡ rào cản này, đưa độ phức tạp về mức \(O(K \cdot N \log N)\), cho phép thuật toán chạy mượt mà chỉ trong vài trăm mili-giây!

TỐI ƯU QUY HOẠCH ĐỘNG CHIA ĐỂ TRỊ (DIVIDE & CONQUER DP) Tính đơn điệu của điểm chuyển trạng thái opt[i, j] ≤ opt[i, j+1] giúp giảm O(K*N²) về O(K*N log N) Cây đệ quy phân rã miền tìm kiếm opt Tính mid = N / 2Vùng tìm kiếm: [1 ... N] → opt_mid Nửa trái [L ... mid-1]opt ∈ [opt_L ... opt_mid] Nửa phải [mid+1 ... R]opt ∈ [opt_mid ... opt_R] Độ sâu cây đệ quy: log₂ N tầngMỗi tầng duyệt tổng cộng ≤ 2N điểm cắt ⇒ O(N log N) cho mỗi lớp i Điều kiện áp dụng thuật toán BẤT ĐẲNG THỨC TỨ GIÁC: C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) với mọi a ≤ b ≤ c ≤ d⇒ Đảm bảo tính đơn điệu của opt! SO SÁNH THỜI GIAN THỰC THI: • Quy hoạch động gốc: O(K · N²) • Chia để trị tối ưu: O(K · N log N) KẾT LUẬN VÀ BỘ NHỚ: Bộ nhớ chỉ cần 2 mảng dp_prev và dp_curr: O(N) • Không cần lưu bảng 2 chiều K * N.
CHIA ĐỂ TRỊ DP (D&C DP) Tối ưu điểm chuyển trạng thái đơn điệu 1. Chia đôi miền tính toán Tính mid = (L + R) / 2 Tìm opt_mid ∈ [opt_L ... opt_R] Nửa trái [L .. mid-1] opt ≤ opt_mid Nửa phải [mid+1 .. R] opt ≥ opt_mid → Cây đệ quy có đúng log₂ N tầng ĐIỀU KIỆN ÁP DỤNG: C(a, c) + C(b, d) ≤ C(a, d) + C(b, c) Đảm bảo opt[i, j] ≤ opt[i, j+1] Áp dụng cho bài toán phân hoạch K đoạn. HIỆU QUẢ TỐI ƯU: • Thời gian: O(K · N log N) thay vì O(K · N²) • Bộ nhớ: Chỉ cần 2 mảng 1D dp_prev & dp_curr
Cây đệ quy chia để trị thu hẹp không gian tìm kiếm điểm tối ưu opt(i, j) và tính chất đơn điệu của ma trận Monge.

Điều kiện cần và đủ: Tính đơn điệu của điểm tối ưu

Để áp dụng được kỹ thuật chia để trị, bài toán bắt buộc phải thỏa mãn tính chất đơn điệu của điểm chuyển trạng thái tối ưu (Optimal Decision Monotonicity).

Gọi \(\text{opt}(i, j)\) là giá trị \(k\) nhỏ nhất giúp biểu thức \(dp[i - 1][k] + C(k + 1, j)\) đạt giá trị cực tiểu: \[\text{opt}(i, j) = \arg\min_{0 \le k \le j - 1} \{ dp[i - 1][k] + C(k + 1, j) \}\]

Điều kiện đơn điệu phát biểu rằng: Khi điểm kết thúc \(j\) dịch chuyển sang phải (\(j\) tăng dần), thì điểm cắt tối ưu \(k\) cũng chỉ có thể đứng yên hoặc dịch chuyển sang phải, không bao giờ quay ngược về bên trái:

\[\text{opt}(i, j) \le \text{opt}(i, j + 1) \quad \forall 1 \le j \lt N\]

Bất đẳng thức tứ giác (Quadrangle Inequality)

Làm thế nào để biết một hàm chi phí \(C(l, r)\) có thỏa mãn tính đơn điệu của \(\text{opt}\) hay không? Các nhà toán học đã chỉ ra rằng: Nếu hàm chi phí \(C(l, r)\) thỏa mãn Bất đẳng thức tứ giác (Quadrangle Inequality):

\[C(a, c) + C(b, d) \le C(a, d) + C(b, c) \quad \forall a \le b \le c \le d\]

thì hàm mục tiêu quy hoạch động \(dp[i][j]\) chắc chắn sẽ thỏa mãn tính đơn điệu \(\text{opt}(i, j) \le \text{opt}(i, j + 1)\)!

Ý nghĩa hình học của bất đẳng thức tứ giác: Chi phí của hai đoạn lồng nhau \(([a, d]\) chứa \([b, c])\) luôn lớn hơn hoặc bằng chi phí của hai đoạn đan xen \(([a, c]\) và \([b, d])\). Các hàm chi phí phổ biến trong thi đấu thỏa mãn điều kiện này bao gồm:

  • Bình phương tổng đoạn \(C(l, r) = (pref[r] - pref[l - 1])^2\), với điều kiện mọi phần tử \(a_i \ge 0\). Nếu dãy có số âm, bất đẳng thức tứ giác có thể sai và chia để trị cho đáp số sai: với \(a = [5, 6, 9, -5]\) và \(K = 2\), cách cắt tốt nhất là \([5]\) và \([6, 9, -5]\) với chi phí \(25 + 100 = 125\), nhưng chia để trị in ra \(137\).
  • Hàm đếm số cặp nghịch thế (Inversion Count) trong đoạn \([l, r]\).
  • Hàm khoảng cách hoặc chi phí di chuyển tuyến tính.

Thuật toán chia để trị phân rã miền tìm kiếm

Thông thường, ta tính các giá trị \(dp[i][j]\) tuần tự từ \(j = 1\) đến \(N\). Nhưng chính thứ tự tuần tự này khiến ta không tận dụng được tính đơn điệu. Ý tưởng đột phá của Divide and Conquer DP là: Tính giá trị tại vị trí chính giữa trước, rồi dùng nó để chia đôi không gian tìm kiếm cho hai nửa còn lại!

Tại mỗi tầng \(i\) cố định (từ \(1\) đến \(K\)), ta xây dựng một hàm đệ quy: compute(l, r, opt_l, opt_r)

Trong đó:

  • \([l, r]\) là khoảng các vị trí \(j\) cần tính giá trị \(dp[i][j]\).
  • \([\mathrm{opt\_l}, \mathrm{opt\_r}]\) là khoảng không gian tìm kiếm chứa điểm cắt tối ưu \(\text{opt}(i, j)\) cho mọi \(j \in [l, r]\).

Các bước thực hiện của hàm compute:

  1. Xét phần tử ở giữa: Lấy chỉ số trung tâm \(mid = (l + r) / 2\).
  2. Tìm nghiệm tối ưu cho \(mid\) bằng cách duyệt trâu: Vì ta biết chắc chắn \(\text{opt}(i, mid)\) phải nằm trong đoạn \([\mathrm{opt\_l}, \mathrm{opt\_r}]\), ta chỉ cần duyệt biến \(k\) trong đoạn: \[k \in [\mathrm{opt\_l}, \min(mid - 1, \mathrm{opt\_r})]\] để tìm ra giá trị \(k\) làm cho \(dp[i - 1][k] + C(k + 1, mid)\) đạt cực tiểu. Gọi giá trị tối ưu này là \(best\_k\). Gán \(dp[i][mid]\) và xác định \(\text{opt}(i, mid) = best\_k\).
  3. Phân rã không gian tìm kiếm cho nửa bên trái:
    • Với mọi \(j \in [l, mid - 1]\), do tính đơn điệu nên \(\text{opt}(i, j) \le \text{opt}(i, mid) = best\_k\).
    • Ta gọi đệ quy xử lý nửa trái: compute(l, mid - 1, opt_l, best_k).
  4. Phân rã không gian tìm kiếm cho nửa bên phải:
    • Với mọi \(j \in [mid + 1, r]\), do tính đơn điệu nên \(\text{opt}(i, j) \ge \text{opt}(i, mid) = best\_k\).
    • Ta gọi đệ quy xử lý nửa phải: compute(mid + 1, r, best_k, opt_r).

Cứ như vậy, không gian tìm kiếm cho các bài toán con bị thu hẹp đáng kể sau mỗi tầng đệ quy!

Chứng minh độ phức tạp O(K * N log N)

Hãy phân tích thời gian chạy của hàm compute cho một tầng \(i\):

  • Cây đệ quy có độ sâu tối đa là \(\lceil \log_2 N \rceil\) vì mỗi lần ta chia đôi đoạn \([l, r]\) thành hai nửa.
  • Tại một độ sâu bất kỳ của cây đệ quy:
    • Tập hợp các đoạn \([l, r]\) tạo thành một phân hoạch của đoạn \([1, N]\).
    • Tập hợp các khoảng tìm kiếm \([\mathrm{opt\_l}, \mathrm{opt\_r}]\) của các lời gọi hàm ở cùng một độ sâu chỉ chồng lấn lên nhau tối đa tại các điểm biên \(best\_k\).
    • Do đó, tổng số bước lặp kiểm tra \(k\) trên toàn bộ các lời gọi hàm tại cùng một độ sâu bị chặn trên bởi: \[\sum (\mathrm{opt\_r} - \mathrm{opt\_l} + 1) \le 2N\]
  • Vì có tối đa \(O(\log N)\) tầng đệ quy, tổng thời gian tính toán cho toàn bộ một tầng \(i\) là: \[O(N \log N)\]

Với \(K\) tầng trạng thái cần tính toán, tổng thời gian toàn bộ thuật toán là: \[O(K \cdot N \log N)\] So với độ phức tạp ban đầu \(O(K \cdot N^2)\), thuật toán đã giảm được một thừa số \(N / \log N\), tức là tăng tốc độ chạy lên tới hàng nghìn lần!

Học cùng giảng viên

Chủ đề này nằm trong Buổi 12 - DP Bitmask + DP on Tree của Tài năng lập trình. Xem đề cương

Cài đặt chuẩn C++17 và Python 3

Dưới đây là lời giải mẫu hoàn chỉnh bằng kỹ thuật Chia để trị DP cho bài toán: chia dãy \(N\) số nguyên không âm thành đúng \(K\) đoạn liên tiếp sao cho tổng các bình phương tổng từng đoạn là nhỏ nhất.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Tối ưu quy hoạch động chia để trị (Divide and Conquer DP)
// Giảm độ phức tạp từ O(K * N^2) xuống O(K * N log N)
const long long INF = 2e18;

int n, k;
vector<long long> a, pref;
vector<long long> dp_prev, dp_curr;

// Hàm chi phí: Tổng bình phương đoạn [l, r]
long long cost(int l, int r) {
    long long s = pref[r] - pref[l - 1];
    return s * s;
}

// Hàm chia để trị tính dp_curr[l...r] với vùng tối ưu opt nằm trong [opt_l...opt_r]
void compute(int l, int r, int opt_l, int opt_r) {
    if (l > r) return;

    int mid = l + (r - l) / 2;
    long long best_val = INF;
    int best_opt = -1;

    // Duyệt qua vùng nghiệm khả dĩ của opt
    int limit = min(mid, opt_r);
    for (int p = opt_l; p <= limit; p++) {
        long long current_val = dp_prev[p - 1] + cost(p, mid);
        if (current_val < best_val) {
            best_val = current_val;
            best_opt = p;
        }
    }

    dp_curr[mid] = best_val;

    // Nhờ tính đơn điệu opt[mid - 1] <= opt[mid] <= opt[mid + 1]
    compute(l, mid - 1, opt_l, best_opt);
    compute(mid + 1, r, best_opt, opt_r);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> k)) return 0;

    a.assign(n + 1, 0);
    pref.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    dp_prev.assign(n + 1, INF);
    dp_curr.assign(n + 1, INF);

    // Cơ sở quy hoạch động: Chia thành 1 đoạn
    for (int j = 1; j <= n; j++) {
        dp_prev[j] = cost(1, j);
    }

    // Tính lần lượt từ 2 đến K đoạn
    for (int i = 2; i <= k; i++) {
        compute(i, n, i, n);
        dp_prev = dp_curr;
    }

    cout << dp_prev[n] << "\n";

    return 0;
}

Các lưu ý thực chiến và kỹ thuật tối ưu bộ nhớ

  1. Tối ưu không gian bộ nhớ bằng mảng hai hàng (Rolling Array): Trạng thái tầng thứ \(i\) chỉ phụ thuộc trực tiếp vào kết quả của tầng thứ \(i - 1\). Do đó, thay vì cấp phát bảng hai chiều \(K \times N\) gây tốn bộ nhớ, ta chỉ cần hai mảng một chiều kích thước \(N\): dp_cur và dp_prev. Sau khi hoàn thành một tầng \(i\), ta gán dp_prev = dp_cur và xóa sạch dp_cur để tái sử dụng. Bộ nhớ được tối ưu từ \(O(K \cdot N)\) xuống chỉ còn \(O(N)\)!
  2. Tránh khởi tạo sai khoảng biên opt: Khi gọi hàm lần đầu cho toàn dải, cần truyền đúng: compute(1, n, 0, n - 1). Lưu ý rằng điểm cắt \(k = 0\) mang ý nghĩa đoạn thứ nhất bắt đầu từ vị trí \(1\) (tiền tố rỗng có chi phí bằng \(0\)).
  3. Hàm chi phí không tính được trong O(1): Nếu hàm \(C(l, r)\) không có công thức giải tích trực tiếp trong \(O(1)\) (ví dụ bài toán đếm số cặp nghịch thế), ta có thể tích hợp kỹ thuật con trỏ trượt của thuật toán Mo. Do quá trình đệ quy chia để trị di chuyển các biên \(l\) và \(r\) có trật tự, tổng số bước di chuyển của hai con trỏ trên toàn cây đệ quy vẫn bị chặn trong giới hạn \(O(N \log N)\).

Luyện ngay trên Big-O Coding

Để nắm vững kỹ thuật Chia để trị DP và chinh phục các bài toán phân hoạch nâng cao, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:

Kỹ thuật Chia để trị DP khác gì so với tối ưu Knuth?

Cả hai kỹ thuật đều khai thác tính chất bất đẳng thức tứ giác (Quadrangle Inequality). Tuy nhiên:

  • Chia để trị DP: Áp dụng cho các bài toán phân hoạch dãy thành \(K\) đoạn độc lập, công thức có dạng \(dp[i][j] = \min_k \{ dp[i-1][k] + C(k+1, j) \}\). Giảm từ \(O(K \cdot N^2)\) về \(O(K \cdot N \log N)\).
  • Tối ưu Knuth: Áp dụng cho các bài toán quy hoạch động trên đoạn con (Interval DP) như bài toán cây tìm kiếm nhị phân tối ưu (không dùng được cho bài nhân chuỗi ma trận, vì chi phí \(p_{i-1} p_k p_j\) phụ thuộc điểm cắt \(k\)), có dạng \(dp[i][j] = \min_k \{ dp[i][k] + dp[k+1][j] \} + C(i, j)\). Giảm từ \(O(N^3)\) về \(O(N^2)\).
Nếu hàm chi phí C(l, r) không tính được trong O(1) thì có áp dụng D&C DP được không?

Hoàn toàn được! Như đã phân tích, bạn có thể duy trì hai con trỏ toàn cục cur_l và cur_r tương tự như thuật toán Mo. Khi hàm compute cần giá trị \(C(k + 1, mid)\), bạn dịch chuyển hai con trỏ tới đoạn tương ứng và cập nhật kết quả. Tổng số lần dịch chuyển con trỏ trong toàn bộ quá trình đệ quy chia để trị chỉ là \(O(K \cdot N \log N)\).

Làm thế nào để kiểm tra tính đơn điệu trong phòng thi mà không cần chứng minh toán học phức tạp?

Trong phòng thi, nếu nghi ngờ bài toán có thể tối ưu bằng D&C DP nhưng việc chứng minh bất đẳng thức tứ giác quá nặng nề:

  1. Bạn hãy viết một hàm giải trâu \(O(N^2)\) trên bộ test nhỏ (\(N = 100\)).
  2. Lưu lại mảng \(\text{opt}(i, j)\) cho mọi \(j\).
  3. Viết vòng lặp kiểm tra xem điều kiện \(\text{opt}(i, j) \le \text{opt}(i, j + 1)\) có luôn đúng với mọi \(j\) hay không. Nếu điều kiện luôn thỏa mãn trên hàng chục test ngẫu nhiên, bạn có thể tự tin 99% triển khai ngay thuật toán Chia để trị DP!

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483