DP khoảng (Interval DP)

DP khoảng (Interval DP) là kỹ thuật quy hoạch động mà mỗi trạng thái mô tả một đoạn con liền nhau $[l,r]$ của dãy. Lời giải cho một đoạn dài được ghép từ lời giải của các đoạn con ngắn hơn. Nhờ đó, thay vì duyệt mọi cách chia đoạn (cấp số mũ), ta tính được kết quả tối ưu trong $O(N^3)$ thời gian và $O(N^2)$ bộ nhớ.

Đây là khuôn mẫu chuẩn cho các bài kiểu "nhân dãy ma trận", "gộp đá", "nổ bóng", "đặt dấu ngoặc", "trò chơi hai người trên dãy"... — những bài mà kết quả phụ thuộc vào thứ tự xử lý hoặc điểm chia trên một dãy có thứ tự.

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

Một bài có khả năng cao là Interval DP nếu:

• Dữ liệu là một dãy / chuỗi có thứ tự cố định (không được sắp xếp lại).
• Một thao tác làm hai đầu mút co lại, hoặc tách đoạn thành hai phần $[l,k]$ và $[k+1,r]$.
• Kết quả của đoạn lớn được suy ra từ kết quả các đoạn con và một chi phí ghép $\text{cost}(l,r,k)$.
• $N$ thường nhỏ ($N\le 500$ hoặc vài nghìn), gợi ý độ phức tạp bậc ba chấp nhận được.

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

Câu hỏi mấu chốt của mọi bài Interval DP là: "phép tính cuối cùng (hoặc đầu tiên) trên đoạn $[l,r]$ là gì?"

Hãy gọi dp[l][r] là kết quả tối ưu cho riêng đoạn $[l,r]$. Trong mọi cách xử lý đoạn này, luôn tồn tại một điểm chia $k$ — chẳng hạn vị trí ngoặc ngoài cùng, viên đá gộp cuối, hay quả bóng nổ cuối. Khi đã cố định $k$, bài toán vỡ ra thành hai đoạn con độc lập $[l,k]$ và $[k+1,r]$ (hoặc $[l,k-1]$ và $[k+1,r]$), cộng thêm chi phí ghép hai phần đó lại.

$$dp[l][r]=\underset{l\le k<r}{\text{opt}}(dp[l][k]+dp[k+1][r]+\text{cost}(l,r,k))$$

Tính đúng đắn dựa trên hai điều:

1. Tính chất con tối ưu (optimal substructure): một cách ghép tối ưu cho $[l,r]$ buộc phải dùng cách ghép tối ưu cho hai nửa của nó — nếu một nửa chưa tối ưu, ta thay bằng phương án tốt hơn mà không ảnh hưởng nửa kia, mâu thuẫn.
2. Tính độc lập sau khi cố định điểm chia: hai đoạn con không "đè" lên nhau, nên có thể tối ưu riêng rẽ.

Vì dp[l][r] luôn cần các đoạn ngắn hơn đã có sẵn, ta phải tính theo độ dài đoạn tăng dần. Đoạn dài 1 là cơ sở (thường bằng 0 hoặc giá trị đơn lẻ), rồi mở rộng dần ra đoạn dài $N$.

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

// dp[l][r] = kết quả tối ưu cho đoạn [l, r]
for (int len = 2; len <= n; len++) {          // độ dài đoạn tăng dần
    for (int l = 0; l + len - 1 < n; l++) {   // đầu trái
        int r = l + len - 1;                  // đầu phải
        dp[l][r] = INF;                       // hoặc -INF nếu tìm max
        for (int k = l; k < r; k++) {         // thử mọi điểm chia
            dp[l][r] = min(dp[l][r],
                           dp[l][k] + dp[k+1][r] + cost(l, r, k));
        }
    }
}
// đáp số: dp[0][n-1]

Điểm cốt lõi: vòng len phải ở ngoài cùng. Nếu duyệt l, r trực tiếp mà không đảm bảo đoạn con ngắn hơn được tính trước, kết quả sẽ sai.

Ví dụ chạy tay: Gộp đá (Stone Merging)

Bài toán: Có $N$ đống đá xếp thành hàng, khối lượng $a=[4,3,5,1]$. Mỗi lần gộp hai đống liền kề thành một đống, chi phí bằng tổng khối lượng hai đống đó. Tìm tổng chi phí nhỏ nhất để gộp tất cả thành một đống.

Đặt sum[l][r] = tổng khối lượng đoạn $[l,r]$ (chi phí của bước gộp cuối cùng trên đoạn này, vì bước cuối luôn gộp hết đoạn lại). Khi đó:

$$dp[l][r]={min}_{l\le k<r}(dp[l][k]+dp[k+1][r])+\text{sum}[l][r]$$

Bảng tiền tố tổng: $\text{sum}[l][r]$ với chỉ số 0-based, $a=[4,3,5,1]$.

Khởi tạo đoạn dài 1: dp[i][i] = 0 (một đống không tốn chi phí).

len = 2:

dp[0][1]: gộp {4,3}  -> cost = sum=7         => 7
dp[1][2]: gộp {3,5}  -> cost = sum=8         => 8
dp[2][3]: gộp {5,1}  -> cost = sum=6         => 6

len = 3 (sum[0..2]=12, sum[1..3]=9):

dp[0][2] = min( dp[0][0]+dp[1][2],   k=0 -> 0+8 = 8
                dp[0][1]+dp[2][2] )  k=1 -> 7+0 = 7   + sum=12 => 19
dp[1][3] = min( dp[1][1]+dp[2][3],   k=1 -> 0+6 = 6
                dp[1][2]+dp[3][3] )  k=2 -> 8+0 = 8   + sum=9  => 15

len = 4 (sum[0..3]=13) — ô đích [*]:

        r=0   r=1   r=2   r=3
 l=0 |   0  |  7  | 19  | [*] |
 l=1 |      |  0  |  8  | 15  |
 l=2 |      |     |  0  |  6  |
 l=3 |      |     |     |  0  |

dp[0][3] = min( dp[0][0]+dp[1][3],   k=0 -> 0 +15 = 15
                dp[0][1]+dp[2][3],   k=1 -> 7 + 6 = 13  <-- nhỏ nhất
                dp[0][2]+dp[3][3] )  k=2 -> 19+ 0 = 19
              + sum[0][3]=13
            = 13 + 13 = 26

Đáp số dp[0][3] = 26. Để ý cách bảng được lấp theo đường chéo từ trong ra ngoài: mọi ô cần dùng (như [0][1], [2][3]) đều đã có giá trị trước khi tính ô góc trên-phải.

Cài đặt

Bài Gộp đá đầy đủ (C++):

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), pre(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pre[i + 1] = pre[i] + a[i];        // tiền tố để lấy sum[l][r] trong O(1)
    }
    auto sum = [&](int l, int r) { return pre[r + 1] - pre[l]; };

    // dp[l][r]: chi phí nhỏ nhất gộp đoạn [l, r] thành một đống
    vector<vector<long long>> dp(n, vector<long long>(n, 0));

    for (int len = 2; len <= n; len++) {       // độ dài đoạn tăng dần
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            dp[l][r] = LLONG_MAX;
            for (int k = l; k < r; k++) {       // điểm chia: bước gộp cuối tách [l,k] | [k+1,r]
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
            }
            dp[l][r] += sum(l, r);              // cộng chi phí gộp hai phần thành một
        }
    }
    cout << dp[0][n - 1] << "\n";
}

Một ví dụ kinh điển khác — Nhân dãy ma trận (Matrix Chain), ma trận $A_i$ kích thước $p_{i-1}\times p_i$, dùng chỉ số 1-based:

// p[0..n], dp[l][r] = số phép nhân vô hướng ít nhất cho A_l..A_r
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++) {
            // cost ghép: nhân khối kết quả (p[l-1] x p[k]) với (p[k] x p[r])
            long long c = dp[l][k] + dp[k+1][r] + (long long)p[l-1]*p[k]*p[r];
            dp[l][r] = min(dp[l][r], c);
        }
    }
}
cout << dp[1][n] << "\n";

Với bài kiểu nổ bóng / xoá đoạn, đôi khi tiện hơn khi cố định phần tử xử lý cuối cùng $k$ trong đoạn, chia thành $[l,k-1]$ và $[k+1,r]$:

$$dp[l][r]={max}_{l\le k\le r}(dp[l][k-1]+dp[k+1][r]+\text{gain}(l,k,r))$$

Độ phức tạp

• Thời gian: $O(N^3)$. Có $O(N^2)$ trạng thái dp[l][r] (mọi cặp $l\le r$), mỗi trạng thái duyệt tối đa $N$ điểm chia $k$. Tích lại là $N^2·N=N^3$. Nếu cost(l, r, k) tính được trong $O(1)$ (nhờ tiền tố tổng) thì không phát sinh thêm thừa số.
• Bộ nhớ: $O(N^2)$. Bảng dp hai chiều kích thước $N\times N$. Tiền tố tổng chỉ tốn $O(N)$ nên không đổi cấp.

Lưu ý: nếu cost cần $O(N)$ để tính lại mỗi lần (ví dụ quét lại đoạn), tổng độ phức tạp leo lên $O(N^4)$ — gần như luôn TLE. Hãy tiền xử lý để cost về $O(1)$.

Với một số bài có tính chất tứ giác (quadrangle inequality), kỹ thuật Knuth's optimization đưa được về $O(N^2)$, nhưng đó là chủ đề nâng cao.

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

• Sai thứ tự duyệt. Đây là lỗi số một. Nếu đặt vòng for l ngoài rồi for r trong (theo thứ tự tự nhiên), khi tính dp[l][r] thì dp[k+1][r] với $k+1>l$ chưa được tính. Luôn duyệt theo độ dài đoạn len tăng dần (hoặc l giảm dần kết hợp r tăng dần).

• Tràn số (int overflow). Các bài gộp đá / nhân ma trận có tổng hoặc tích rất lớn (tổng các bước gộp, $p_{l-1}·p_k·p_r$). Dùng int sẽ tràn âm thầm. Khai báo dp là long long, và ép kiểu trước khi nhân: (long long)p[l-1]*p[k]*p[r], không phải (long long)(p[l-1]*p[k]*p[r]).

• Khởi tạo cơ sở sai. Đoạn dài 1 (dp[i][i]) phải đặt đúng: 0 cho bài chi phí gộp, giá trị phần tử cho bài tích luỹ, hay INF/-INF nếu đoạn 1 phần tử là trạng thái không hợp lệ. Quên khởi tạo dẫn tới cộng dồn rác.

• Off-by-one ở điểm chia. Phân biệt rõ hai kiểu chia: kiểu "ghép hai nửa" dùng dp[l][k] + dp[k+1][r] với $k$ chạy $l\le k<r$; kiểu "xử lý phần tử cuối" dùng dp[l][k-1] + dp[k+1][r] với $k$ chạy $l\le k\le r$ (chú ý dp[l][k-1] khi k=l trỏ tới đoạn rỗng — cần định nghĩa cho hợp lệ, thường bằng 0).

• Quên INF khi lấy min mà chưa cập nhật. Nếu để dp[l][r] = 0 rồi min với các phương án dương, kết quả luôn ra 0. Khởi tạo LLONG_MAX (hoặc một số đủ lớn nhưng tránh tràn khi cộng tiếp).

• Tính cost trong $O(N)$. Nếu trong vòng k còn gọi một vòng lặp con để tính tổng đoạn, độ phức tạp âm thầm thành $O(N^4)$. Dùng mảng tiền tố để sum(l, r) về $O(1)$.

Biến thể / Mở rộng

• Cố định điểm cuối thay vì điểm chia (nổ bóng, xoá hộp): nghĩ "phần tử nào xử lý sau cùng" thay vì "đầu tiên".
• DP khoảng trên vòng tròn (circular): nối dãy với chính nó thành độ dài $2N$ rồi xét mọi đoạn độ dài $N$, hoặc cố định một điểm cắt.
• Kết hợp trạng thái phụ: thêm chiều cho màu/người chơi/số nhóm, ví dụ dp[l][r][c].
• Lý thuyết trò chơi (game theory) trên đoạn: hai người lần lượt lấy từ hai đầu, dp[l][r] lưu chênh lệch điểm tối ưu của người đi trước (minimax) — xem bài wandduel bên dưới.
• Liên quan: Quy hoạch động.

Bài tập luyện

• WANDDUEL Đấu Đũa Phép (wandduel) — (Advanced) DP khoảng kết hợp lý thuyết trò chơi (minimax) trên một dãy: trạng thái dp[l][r] là kết quả tối ưu khi chỉ còn đoạn $[l,r]$, điểm vào lý tưởng cho người mới làm quen điểm chia ở hai đầu.
• Trò chơi 248 (game248) — (Veteran) Gộp các phần tử liền kề bằng nhau để tạo giá trị lớn hơn; cần định nghĩa trạng thái khoảng tinh tế và xử lý ghép hai đoạn, rèn kỹ năng thiết kế cost(l, r, k).
• Đảo Ngược Dãy Con (subrev) — (Master) Bài Interval DP khó, đòi hỏi kết hợp đảo đoạn con với trạng thái khoảng và tối ưu chuyển trạng thái — thử thách sau khi đã nắm vững khuôn mẫu cơ bản.