Chương trình tìm ra cây phân tích cú pháp tối thiểu trong C ++

Giả sử chúng ta có một danh sách các số duy nhất và được sắp xếp đại diện cho các điểm ngắt trong một chuỗi. Chúng tôi muốn tạo một cây theo các quy tắc này -

Có các nút có giá trị (a, b) trong đó a và b là các điểm ngắt. Điều này có nghĩa là nút kéo dài từ các chỉ số [a, b] trong chuỗi.
Nút gốc trải dài trên mọi điểm ngắt. (toàn bộ chuỗi).
Các nhịp của nút con bên trái và bên phải được sắp xếp theo thứ tự, liền kề và chứa khoảng của nút cha.
Các nút lá 'chỉ số của' a 'trong các điểm ngắt bằng 1 trước chỉ số của' b 'trong các điểm ngắt.

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

Vì vậy, nếu đầu vào giống như breakpoints =[1, 4, 7, 12], thì đầu ra sẽ là 28.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước của các điểm ngắt mảng đầu vào
nếu n <=1, thì -
- trả về 0
nếu n giống 2 thì -
- trả về điểm ngắt [1] - điểm ngắt [0]
Xác định mảng p [n - 1]
để khởi tạo i:=0, khi tôi
- p [i]:=breakpoints [i + 1]
Xác định một mảng trước [n]
để khởi tạo i:=1, khi i
- pre [i]:=pre [i - 1] + p [i - 1]
Xác định một mảng 2D dp [n, n] và khởi tạo các cột với vô cực.
Xác định một mảng 2D op [n, n]
để khởi tạo i:=1, khi i
- dp [i, i]:=p [i - 1], op [i, i]:=i
để khởi tạo len:=2, khi len
- để khởi tạo i:=1, khi i + len - 1
  - j:=i + len - 1
  - idx:=i
  - để khởi tạo k:=tối đa của (i, op [i, j-1]), khi k
    - chi phí:=dp [i, k] + dp [k + 1, j]
    - nếu giá
      - idx:=k
      - dp [i, j]:=chi phí
  - op [i, j]:=idx
  - dp [i, j]:=dp [i, j] + pre [j] - pre [i - 1]
trả về dp [1, n - 1]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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}

Chương trình tìm ra cây phân tích cú pháp tối thiểu trong C ++

Ví dụ

Đầu vào

Đầu ra