C++에서 최소 구문 분석 트리를 찾는 프로그램

<시간/>

문자열의 중단점을 나타내는 고유하고 정렬된 숫자 목록이 있다고 가정합니다. 우리는 이러한 규칙에서 트리를 만들고 싶습니다 -

값이 (a, b)인 노드가 있으며 여기서 b와 b는 중단점입니다. 이는 노드가 문자열의 인덱스 [a, b]에 걸쳐 있음을 의미합니다.
루트 노드는 모든 중단점에 걸쳐 있습니다. (전체 문자열).
노드의 왼쪽 및 오른쪽 자식 범위는 순서가 지정되고 연속적이며 부모 노드의 범위를 포함합니다.
리프 노드의 중단점에서 'a'의 인덱스는 중단점에서 'b'의 인덱스보다 먼저 1입니다.

트리의 비용은 트리의 모든 노드에 대한 b의 합으로 결정됩니다. 우리의 목표는 실현 가능한 트리의 가능한 가장 낮은 비용을 결정하는 것입니다.

따라서 입력이 breakpoints =[1, 4, 7, 12]와 같으면 출력은 28이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=입력 배열 중단점의 크기
n <=1이면 -
- 0 반환
n이 2와 같으면 -
- 반환 중단점[1] - 중단점[0]
배열 p[n - 1]
정의
initialize i :=0의 경우, i
- p[i] :=중단점[i + 1]
배열 pre[n]
정의
initialize i :=1의 경우, i
- pre[i] :=pre[i - 1] + p[i - 1]
하나의 2D 배열 dp[n, n]을 정의하고 무한대로 열을 초기화합니다.
하나의 2D 배열 op[n, n]
정의
initialize i :=1의 경우, i
- dp[i,i] :=p[i - 1], op[i,i] :=i
len 초기화의 경우:=2, len
- initialize i :=1의 경우, i + len - 1
  - j :=i + len - 1
  - idx :=나는
  - k 초기화의 경우:=(i, op[i,j-1]의 최대값), k <최소값(j - 1, op[i + 1, j])일 때 업데이트(k를 1만큼 증가), 다음을 수행합니다.
    - 비용 :=dp[i, k] + dp[k + 1, j]
    - 비용
      - idx :=k
      - dp[i, j] :=비용
  - 연산[i, j] :=idx
  - dp[i, j] :=dp[i, j] + pre[j] - pre[i - 1]
반환 dp[1, n - 1]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

{1, 4, 7, 12}