Day 115-Q4 | 区間DPの高速化（Knuthの最適化）

問題

$N$ 個の石が一列に並んでおり、$i$ 番目の石の重さは $w_i$ である。1回の操作で隣接する2つの塊を1つに併合でき、そのコストは併合される2つの塊に含まれる石の重さの合計（元の $w$ の総和）である。すべての石を1つの塊にまとめるための最小コストを求めよ（塊は常に連続区間を保ち、順序の入れ替えはできない）。

入力形式

N
w_1 w_2 ... w_N

制約

$1 \le N \le 2000$

$1 \le w_i \le 10^4$

入出力例

入力例1

3
10 20 30

出力例1

$10$と$20$を先に併合するとコスト$30$、残り$\{30,30\}$を併合するとコスト$60$、合計$90$。逆順に$20$と$30$を先に併合するとコスト$50+60=110$で損。$90$が最小。

概念図: 分割点 opt[i][j] の単調な包絡

ヒント（段階的開示）

ヒント1: 方向性

これは「区間分割の最小コストDP」で、$dp[i][j] = \min_{i \le k < j} \left( dp[i][k] + dp[k+1][j] \right) + \text{cost}(i,j)$ という形をしている。愚直に全ての $k$ を試すと $O(N^3)$ になり、$N=2000$ では到底間に合わない。分割点 $k$ の最適値 $opt[i][j]$ に、$i$ や $j$ を動かしたときの単調性がないか考えてみる。

ヒント2: アプローチ

$\text{cost}(i,j)$（区間の重み総和）が「四辺形不等式」$\text{cost}(a,c)+\text{cost}(b,d) \le \text{cost}(a,d)+\text{cost}(b,c)$（$a\le b\le c\le d$）を満たすとき、$opt[i][j-1] \le opt[i][j] \le opt[i+1][j]$ という単調性が成り立つ（Knuthの定理）。各 $(i,j)$ について $k$ を探す範囲を $[opt[i][j-1],\ opt[i+1][j]]$ に絞り込める。区間長の昇順にDPを計算していけば探索範囲の合計はならし解析で $O(N^2)$ に収まる。

ヒント3: 誘導（コード骨格）

# dp[i][i] = 0, opt[i][i] = i を基底として設定
# lengthを2..Nまで増やしながら:
#   for i in range(N - length + 1):
#       j = i + length - 1
#       lo = opt[i][j-1]
#       hi = min(opt[i+1][j], j-1)
#       dp[i][j], opt[i][j] = kを[lo, hi]の範囲だけ試して求める最小値と、その時のk

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    w = [int(data[idx + i]) for i in range(N)]; idx += N

    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + w[i]

    def S(i, j):
        return prefix[j + 1] - prefix[i]

    INF = float('inf')
    dp = [[0] * N for _ in range(N)]
    opt = [[0] * N for _ in range(N)]
    for i in range(N):
        opt[i][i] = i

    for length in range(2, N + 1):
        for i in range(N - length + 1):
            j = i + length - 1
            lo = opt[i][j - 1]
            hi = min(opt[i + 1][j], j - 1)
            if lo > hi:
                lo, hi = hi, lo
            best = INF
            best_k = lo
            base_cost = S(i, j)
            for k in range(lo, hi + 1):
                val = dp[i][k] + dp[k + 1][j] + base_cost
                if val < best:
                    best = val
                    best_k = k
            dp[i][j] = best
            opt[i][j] = best_k

    print(dp[0][N - 1])

main()

計算量: $opt$の単調性により、各$(i,j)$での$k$の探索範囲の合計がならし解析で $O(N^2)$（愚直な$O(N^3)$から改善）。$N=2000$で約$4\times10^6$回の内側ループ。$N \le 300$程度の全ケースで愚直$O(N^3)$実装と結果が一致することを確認済み。

Step-by-Step 解説

1区間の重み和 $S(i,j)$ を累積和で前計算
併合コストは区間の重み総和なので、prefix配列で $O(1)$ 取得できるようにしておく。

2基底 $dp[i][i]=0$, $opt[i][i]=i$ の設定
石1個だけの塊は併合不要でコスト0。分割点の探索範囲を決める際にこの基底値が使われる。

3区間長の昇順に計算する理由
$dp[i][j]$を求めるには$opt[i][j-1]$と$opt[i+1][j]$が両方確定している必要があるため、必ず区間長（length）の昇順にループを回す。

4$k$の探索範囲を$[opt[i][j-1],\ opt[i+1][j]]$に絞る
理論上は$lo\le hi$が保証されるが、境界を考慮してmin/maxで補正しておくと安全。

5計算量が$O(N^2)$になる直感
$opt[i][j]$は$i$を固定して$j$を増やすと単調非減少、$j$を固定して$i$を増やすと単調非増加になる（四辺形不等式から導かれる性質）。この単調性により全体の探索幅の総和が $O(N^2)$ に収まる。

よくあるミス

ミス	原因	正しい書き方
区間長の小さい順ではなく愚直な2重ループで計算してしまう	通常の区間DPの書き方をそのまま流用	$opt[i][j-1]$と$opt[i+1][j]$が両方確定している必要があるため、必ず`length`の昇順に計算する
$k$の探索範囲の下限・上限を取り違える	$opt[i][j-1]$と$opt[i+1][j]$の大小関係を勘違い	理論上$lo \le hi$だが、境界ケースで逆転しうるので実装では`min`/`max`で補正する
cost関数が四辺形不等式を満たさない問題にKnuth最適化を適用してしまう	「区間DPなら何でも高速化できる」と誤解	Knuth最適化が有効なのはcostが四辺形不等式を満たす場合のみ。満たさない場合は分割統治DP最適化（Monge性）等を検討する
$k=j-1$のとき`dp[k+1][j]`が`dp[j][j]`になることを見落とし範囲外と錯覚する	添字の対応関係を追いきれていない	`dp[j][j]=0`が基底として正しく初期化されていれば$k=j-1$でも問題なくアクセスできる

次のステップ

発展: 同じ問題を分割統治DP最適化（Monge性を利用した $O(N \log N)$）で解き、計算量・実装量の違いを比較する
発展: 最適二分探索木問題（探索頻度の期待値を最小化する）に同じ手法を適用してみる
発展: コスト関数が実際に四辺形不等式を満たすかどうかを数値実験で検証するコードを書いてみる

自己評価

完全理解おおむね理解要復習

Day 115-Q4 — 区間DPの高速化（Knuthの最適化・石の併合問題）

問題