找出C ++中最小解析树的程序

假设我们有一个代表字符串中的断点的唯一和排序数字列表。我们想根据这些规则创建一棵树-

• 有些节点的值为(a,b)，其中a和b是断点。这意味着该节点跨越字符串中的索引[a，b]。

• 根节点跨越每个断点。（整个字符串）。

• 节点左右子节点的跨度是有序的，连续的，并且包含父节点的跨度。

• 叶子节点的断点索引“ a”比断点的“ b”索引早1。

一棵树的成本确定为b-a对树中每个节点的总和。我们的目标是确定可行树的最低成本。

因此，如果输入像断点= [1、4、7、12]，则输出将为28。

在线示例

让我们看下面的实现以更好地理解-

#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