C++で最小コストの構文解析木を求める方法：区間DPとKnuthの最適化による効率解法

ソート済みで重複のない数値リストがあり、その各要素は文字列中の「ブレークポイント（区切り位置）」を表していると仮定します。このブレークポイントをもとに、次のルールに従う木を構築することを考えます。

• ノードの値：各ノードは (a, b) という値を持ちます。a と b はいずれもブレークポイントであり、そのノードが文字列のインデックス区間 [a, b] を担当することを意味します。
• ルートノード：根はすべてのブレークポイントを含む、すなわち文字列全体を範囲とします。
• 子ノードの範囲：左の子と右の子の範囲は順序が保たれ、互いに隣接（連続）し、かつ親ノードの範囲をちょうど覆うように分割されます。
• 葉ノード：葉においては、ブレークポイント配列中の a のインデックスが b のインデックスの直前に相当します（＝隣り合う2つのブレークポイントを指します）。

木のコストは、木を構成するすべてのノードについて (b − a) を合計した値として定義されます。目標は、上記の制約を満たす木の中でコストが最小になるものを求めることです。

たとえば入力が breakpoints = [1, 4, 7, 12] の場合、出力は 28 となります。

アプローチ：区間DPとKnuthの最適化

この問題は、オプティマル二分探索木（Optimal Binary Search Tree）と同型の区間分割問題です。ナイーブな区間DPでは O(n³) かかりますが、Knuthの最適化（最適分割位置の単調性）を利用すると O(n²) まで高速化できます。具体的な手順は次のとおりです。

1. n を配列 breakpoints のサイズとします。
2. n ≤ 1 ならば 0 を返します（木を構成する必要がないため）。
3. n == 2 ならば breakpoints[1] − breakpoints[0] を返します（ルート1個のみで構成されるため）。
4. 長さ n−1 の配列 p を作成し、隣接するブレークポイントの間隔 p[i] = breakpoints[i+1] − breakpoints[i] を格納します。
5. 長さ n の累積和配列 pre を作成します（pre[i] = pre[i−1] + p[i−1]）。これにより任意の区間の総コストを O(1) で参照できます。
6. 2次元配列 dp[n][n] を無限大で初期化します。dp[i][j] は「インデックス i〜j のブレークポイントで構成される部分木の最小コスト」を表します。
7. 最適な分割位置 k を記録するための2次元配列 op[n][n] も併せて用意します。
8. 長さ1の区間については、i = 1 … n−1 に対して dp[i][i] = p[i−1]、op[i][i] = i と初期化します。
9. 区間の長さ len を 2 から n−1 まで伸ばしながら、各区間 [i, j]（j = i + len − 1）について、k を max(i, op[i][j−1]) から min(j−1, op[i+1][j]) までの範囲でのみ試行し、dp[i][k] + dp[k+1][j] が最小となる k を求めます。得られた最小値に区間全体のコスト pre[j] − pre[i−1] を加算して dp[i][j] とし、対応する k を op[i][j] に保存します。
10. 最終的に dp[1][n−1] を返します。

なお、dp[i][j] に加算している pre[j] − pre[i−1] は「区間 [i, j] 全体を1つのノードが担うときのコスト（breakpoints[j] − breakpoints[i]）」に相当します。部分木内の各ノードごとにこのコストが一度ずつ課されるため、これで木全体のコスト定義と一致します。

C++での実装例

理解を深めるために、以下の実装をご覧ください。

#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

計算量

Knuthの最適化により、分割位置 k の探索範囲が単調に移動するため、時間計算量は O(n²)、dp・op テーブル分の空間計算量も O(n²) となります。ナイーブな O(n³) の実装と比べて大幅に高速に動作します。