DP khoảng (Interval DP)

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

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

DP khoảng (Interval DP) là kỹ thuật quy hoạch động với trạng thái là một đoạn con $[l, r]$ của dãy. Kết quả cho đoạn lớn được tính từ các đoạn nhỏ hơn.

Nhận dạng bài toán

Dấu hiệu bài Interval DP:

Xử lý trên một dãy / chuỗi có thứ tự.
Kết quả trên đoạn $[l, r]$ phụ thuộc vào cách chia đoạn thành hai phần.
Thường hỏi: tối ưu hóa chi phí, số cách, hay giá trị cực đại/cực tiểu trên toàn dãy.

Cấu trúc tổng quát

dp[l][r] = kết quả tốt nhất cho đoạn [l, r]

Công thức chuyển:

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

Thứ tự tính: Tính theo độ dài đoạn tăng dần (từ ngắn đến dài).

// Duyệt theo độ dài đoạn
for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        dp[l][r] = INF;
        for (int k = l; k < r; k++) {
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l, r, k));
        }
    }
}

Độ phức tạp: $O (N^{3})$ thời gian, $O (N^{2})$ bộ nhớ.

Ví dụ 1: Nhân dãy ma trận (Matrix Chain Multiplication)

Bài toán: Nhân $n$ ma trận $A_{1} \times A_{2} \times \dots \times A_{n}$ sao cho số phép nhân vô hướng là ít nhất. Ma trận $A_{i}$ có kích thước $p_{i - 1} \times p_{i}$ .

Trạng thái: dp[l][r] = chi phí tối thiểu để nhân ma trận từ $l$ đến $r$ .

Chuyển trạng thái: Chọn điểm chia $k$ : nhân hai khối $[l . . k]$ và $[k + 1 . . r]$ .

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

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 0; i <= n; i++) cin >> p[i];

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = LLONG_MAX;
            for (int k = l; k < r; k++) {
                long long cost = dp[l][k] + dp[k+1][r] + (long long)p[l-1] * p[k] * p[r];
                dp[l][r] = min(dp[l][r], cost);
            }
        }
    }

    cout << dp[1][n] << "\n";
}

Ví dụ 2: Phân tích palindrome tối ưu

Bài toán: Cho chuỗi $s$ , tìm số lần cắt tối thiểu để tất cả các phần đều là palindrome.

Cách 1: DP khoảng — dp[l][r] = số cắt tối thiểu cho s[l..r].

Cách 2 (hiệu quả hơn): Tiền xử lý isPalin[l][r] rồi DP 1D.

int n = s.size();
// Tiền xử lý palindrome
vector<vector<bool>> isPalin(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) isPalin[i][i] = true;
for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        if (len == 2) isPalin[l][r] = (s[l] == s[r]);
        else isPalin[l][r] = (s[l] == s[r]) && isPalin[l+1][r-1];
    }
}

// DP 1D: dp[i] = số cắt tối thiểu cho s[0..i]
vector<int> dp(n, INT_MAX);
for (int i = 0; i < n; i++) {
    if (isPalin[0][i]) { dp[i] = 0; continue; }
    for (int j = 1; j <= i; j++) {
        if (isPalin[j][i])
            dp[i] = min(dp[i], dp[j-1] + 1);
    }
}
cout << dp[n-1] << "\n";

Ví dụ 3: Bài toán nổ bóng (Burst Balloons)

Bài toán: Có $n$ bóng với giá trị $a [i]$ . Khi nổ bóng $i$ , nhận điểm $a [l] \cdot a [i] \cdot a [r]$ (với $l, r$ là hai bóng còn lại liền kề). Hỏi điểm tối đa có thể đạt.

Mẹo: Thay vì nghĩ bóng nào nổ trước, nghĩ bóng nào nổ cuối cùng trong đoạn $[l, r]$ .

// Thêm sentinel: a[-1] = a[n] = 1
vector<int> a(n + 2);
a[0] = a[n + 1] = 1;
for (int i = 1; i <= n; i++) cin >> a[i];

vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

for (int len = 1; len <= n; len++) {
    for (int l = 1; l + len - 1 <= n; l++) {
        int r = l + len - 1;
        for (int k = l; k <= r; k++) {
            // k là bóng cuối cùng bị nổ trong [l, r]
            dp[l][r] = max(dp[l][r],
                dp[l][k-1] + a[l-1] * a[k] * a[r+1] + dp[k+1][r]);
        }
    }
}
cout << dp[1][n] << "\n";

Ví dụ 4: Số cách phân tích xâu (Boolean Parenthesization)

Bài toán: Cho biểu thức Boolean gồm $n$ giá trị (T/F) và $n - 1$ toán tử (&, |, ^). Đếm số cách đặt dấu ngoặc để biểu thức có giá trị True.

// dp[l][r] = {số cách True, số cách False} cho đoạn [l, r]
vector<vector<pair<long long,long long>>> dp(n, vector<pair<long long,long long>>(n, {0,0}));

for (int i = 0; i < n; i++)
    dp[i][i] = (vals[i] == 'T') ? make_pair(1LL, 0LL) : make_pair(0LL, 1LL);

for (int len = 2; len <= n; len++) {
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        for (int k = l; k < r; k++) {
            auto [lt, lf] = dp[l][k];
            auto [rt, rf] = dp[k+1][r];
            char op = ops[k];
            if (op == '&') {
                dp[l][r].first  += lt * rt;
                dp[l][r].second += lt * rf + lf * rt + lf * rf;
            } else if (op == '|') {
                dp[l][r].first  += lt * rt + lt * rf + lf * rt;
                dp[l][r].second += lf * rf;
            } else { // '^'
                dp[l][r].first  += lt * rf + lf * rt;
                dp[l][r].second += lt * rt + lf * rf;
            }
        }
    }
}
cout << dp[0][n-1].first << "\n";

Tổng kết

Bài toán	Công thức chuyển
Matrix Chain	$d p [l] [r] = {min}_{k} (d p [l] [k] + d p [k + 1] [r] + p_{l - 1} p_{k} p_{r})$
Optimal BST	$d p [l] [r] = {min}_{k} (d p [l] [k - 1] + d p [k + 1] [r] + w [l] [r])$
Burst Balloons	$d p [l] [r] = {max}_{k} (d p [l] [k - 1] + a [l - 1] \cdot a [k] \cdot a [r + 1] + d p [k + 1] [r])$
Stone Merging	$d p [l] [r] = {min}_{k} (d p [l] [k] + d p [k + 1] [r] + sum [l] [r])$

Nhớ: Luôn duyệt theo độ dài đoạn tăng dần để đảm bảo các đoạn con đã được tính trước.

Bình luận

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