資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：尋找最小解析樹
假設我們有一列獨特的已排序數字，它們代表字串中的斷點。我們想要根據這些規則建立一個樹：
節點具有值 (a, b)，其中 a 和 b 是斷點。這意味著該節點跨越字串中的索引 [a, b]。
根節點跨越所有斷點（整個字串）。
節點的左子節點和右子節點的跨度是有序的、連續的，並且包含父節點的跨度。
葉節點中斷點'a'的索引比斷點'b'的索引小1。
樹的成本定義為樹中每個節點的 b - a 之和。我們的目標是確定可行樹的最低可能成本。
因此，如果輸入類似於breakpoints = [1, 4, 7, 12]，則輸出將為 28。
為了解決這個問題，我們將遵循以下步驟：
n := 輸入陣列breakpoints的大小
如果 n <= 1，則：
返回 0
如果 n 等於 2，則：
返回 breakpoints[1] - breakpoints[0]
定義一個數組 p[n - 1]
對於初始化 i := 0，當 i < n - 1，更新（i 加 1），執行：
p[i] := breakpoints[i + 1]
定義一個數組 pre[n]
對於初始化 i := 1，當 i < n，更新（i 加 1），執行：
pre[i] := pre[i - 1] + p[i - 1]
定義一個二維陣列 dp[n, n] 並將列初始化為無窮大。
定義一個二維陣列 op[n, n]
對於初始化 i := 1，當 i < n，更新（i 加 1），執行：
dp[i,i] := p[i - 1], op[i,i] := i
對於初始化 len := 2，當 len < n，更新（len 加 1），執行：
對於初始化 i := 1，當 i + len - 1 < n，更新（i 加 1），執行：
j := i + len - 1
idx := i
對於初始化 k := max(i, op[i,j-1])，當 k < min(j - 1, op[i + 1, j])，更新（k 加 1），執行：
cost := dp[i, k] + dp[k + 1, j]
如果 cost < dp[i, j]，則：
idx := k
dp[i, j] := cost
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
瀏覽量：331
