Chương trình tìm cây phân tích cú pháp có chi phí nhỏ nhất trong C++

Mô tả bài toán

Cho một danh sách các số duy nhất và đã sắp xếp đại diện cho các điểm ngắt (breakpoints) trong một chuỗi. Chúng ta muốn xây dựng một cây từ các quy tắc sau:

• Mỗi nút có giá trị (a, b) với a, b là các điểm ngắt. Nút này bao phủ từ chỉ số a đến b trong chuỗi.
• Nút gốc bao phủ tất cả các điểm ngắt (toàn bộ chuỗi).
• Khoảng của nút con trái và phải được sắp xếp, liên tiếp và chứa khoảng của nút cha.
• Đối với nút lá, chỉ số của a trong mảng điểm ngắt nhỏ hơn 1 so với chỉ số của b.

Chi phí của cây được xác định là tổng của (b - a) cho mọi nút trong cây. Mục tiêu là tìm chi phí thấp nhất có thể của một cây khả thi.

Ví dụ: với breakpoints = [1, 4, 7, 12], kết quả là 28.

Giải thuật

1. n := kích thước mảng breakpoints.
2. Nếu n ≤ 1, trả về 0.
3. Nếu n = 2, trả về breakpoints[1] - breakpoints[0].
4. Tạo mảng p[n-1] với p[i] = breakpoints[i+1] - breakpoints[i].
5. Tạo mảng tiền tố pre[n] với pre[i] = pre[i-1] + p[i-1].
6. Khởi tạo mảng dp[n][n] với giá trị vô cực và mảng op[n][n].
7. Đặt dp[i][i] = p[i-1], op[i][i] = i cho i từ 1 đến n-1.
8. Duyệt độ dài len từ 2 đến n-1:
   • Với mỗi i sao cho i + len - 1 < n, đặt j = i + len - 1.
   • Duyệt k từ max(i, op[i][j-1]) đến min(j-1, op[i+1][j]).
   • Tính cost = dp[i][k] + dp[k+1][j]. Cập nhật dp[i][j] và op[i][j] nếu cost nhỏ hơn.
   • Sau vòng lặp k, dp[i][j] += pre[j] - pre[i-1].
9. Trả về dp[1][n-1].

Ví dụ minh họa (C++)

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

int solve(vector<int>& breakpoints) {
    int n = breakpoints.size();
    if (n <= 1) return 0;
    if (n == 2) return breakpoints[1] - breakpoints[0];
    vector<int> p(n - 1);
    for (int i = 0; i < n - 1; ++i) p[i] = breakpoints[i + 1] - breakpoints[i];
    vector<int> pre(n);
    for (int i = 1; i < n; ++i) pre[i] = pre[i - 1] + p[i - 1];
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    vector<vector<int>> op(n, vector<int>(n));
    for (int i = 1; i < n; ++i) dp[i][i] = p[i - 1], op[i][i] = i;
    for (int len = 2; len < n; ++len) {
        for (int i = 1; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            int idx = i;
            for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
                int cost = dp[i][k] + dp[k + 1][j];
                if (cost < dp[i][j]) {
                    idx = k;
                    dp[i][j] = cost;
                }
            }
            op[i][j] = idx;
            dp[i][j] += pre[j] - pre[i - 1];
        }
    }
    return dp[1][n - 1];
}

int main() {
    vector<int> breakpoints = {1, 4, 7, 12};
    cout << solve(breakpoints) << endl;
    return 0;
}

Đầu vào

{1, 4, 7, 12}

Đầu ra

28