UVa 10304 最優二叉搜索樹：動態規劃優化詳解

問題描述

給定 n 個有序元素 e1 < e2 < ... < en 及其查詢頻率 f1, f2, ..., fn，構造一棵二叉搜索樹，使得總查詢成本最小。成本定義為：Σ fi * cost(ei)，其中 cost(ei) 為從根節點到該節點的邊數（即深度）。輸出最小總成本。

輸入包含多行，每行以 n 開頭 (1 ≤ n ≤ 250)，後接 n 個非負整數頻率 (0 ≤ fi ≤ 100)。輸出每行對應一個實例的最小成本。

樣例

輸入：
1 5
3 10 10 10
3 5 10 20

輸出：
0
20
20

動態規劃分析

狀態定義

設 dp[i][j] 表示由第 i 到第 j 個元素構成的最優子樹的最小成本（不包含上層深度貢獻）。

遞推關係

若選擇第 k 個元素 (i ≤ k ≤ j) 作為根，則左子樹包含 [i, k-1]，右子樹包含 [k+1, j]。左、右子樹中所有節點深度均增加 1，因此額外成本為左右子樹頻率之和。故：

dp[i][j] = min_{k=i..j} { dp[i][k-1] + dp[k+1][j] + sum(i, k-1) + sum(k+1, j) }

其中 sum(l, r) 為頻率前綴和差值，可 O(1) 計算。邊界：dp[i][i-1] = 0（空樹）。

優化關鍵

初始想法可能引入「層數」作為第三維度，導致 O(n^3) 狀態且轉移 O(n)，總複雜度 O(n^4) 會 TLE。通過觀察發現，每增加一層深度，該子樹所有節點成本均增加其頻率之和，因此可將層數維度消除，直接在二維 DP 中累加頻率和。最終複雜度 O(n^3)，n=250 時約 1.5e7 次操作，配合記憶化搜索或迭代 DP 均可通過。

AC 代碼 (C++，記憶化搜索)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 255;
const int INF = 0x3f3f3f3f;
int n, freq[MAXN], prefix[MAXN];
int dp[MAXN][MAXN];

int dfs(int l, int r) {
    if (l > r) return 0;
    int &res = dp[l][r];
    if (res != INF) return res;
    for (int k = l; k <= r; ++k) {
        int cost = dfs(l, k-1) + dfs(k+1, r) 
                 + prefix[k-1] - prefix[l-1] 
                 + prefix[r] - prefix[k];
        res = min(res, cost);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n) {
        prefix[0] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> freq[i];
            prefix[i] = prefix[i-1] + freq[i];
        }
        memset(dp, 0x3f, sizeof(dp));
        cout << dfs(1, n) << '\n';
    }
    return 0;
}

總結

本題展示了如何通過「換根視角」將三維 DP 降為二維：不再顯式追蹤深度，而是利用頻率和直接計算深度增加帶來的成本增量。這是樹形 DP 中常見的優化技巧，值得熟練掌握。