C++で最小の構文解析ツリーを見つけるためのプログラム

文字列内のブレークポイントを表す一意のソートされた番号のリストがあるとします。これらのルールからツリーを作成したい-

• 値（a、b）を持つノードがあり、aとbはブレークポイントです。これは、ノードが文字列内のインデックス[a、b]にまたがることを意味します。

• ルートノードはすべてのブレークポイントにまたがっています。 （文字列全体）。

• ノードの左右の子のスパンは順序付けられ、連続しており、親ノードのスパンが含まれています。

• ブレークポイントの「a」のリーフノードのインデックスは、ブレークポイントの「b」のインデックスの前に1です。

ツリーのコストは、ツリー内のすべてのノードのb-aの合計として決定されます。私たちの目標は、実現可能なツリーの可能な限り低いコストを決定することです。

したがって、入力がブレークポイント=[1、4、7、12]のような場合、出力は28になります。

これを解決するには、次の手順に従います-

• n：=入力配列ブレークポイントのサイズ

• n <=1の場合、-

  • 0を返す

• nが2と同じ場合、-

  • ブレークポイントを返す[1]-ブレークポイント[0]

• 配列を定義するp[n-1]

• 初期化i：=0の場合、i

  • p [i]：=ブレークポイント[i + 1]

• 配列pre[n]

  を定義します

• 初期化i：=1の場合、i

  • pre [i]：=pre [i-1] + p [i-1]

• 1つの2D配列dp[n、n]を定義し、列を無限大で初期化します。

• 1つの2D配列op[n、n]

  を定義します

• 初期化i：=1の場合、i

  • dp [i、i]：=p [i-1]、op [i、i]：=i

• 初期化len：=2の場合、len

  • 初期化i：=1の場合、i + len --1

    • j：=i + len-1

    • idx：=i

    • 初期化k：=最大（i、op [i、j-1]）の場合、k <最小（j -1、op [i + 1、j]）の場合、更新（kを1増やします）、do −

      • コスト：=dp [i、k] + dp [k + 1、j]

      • コストが

        • idx：=k

        • dp [i、j]：=コスト

    • op [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}

出力

28