Pythonで木棒を切断する最小コストを求めるプログラム|区間DPによる効率的な解法

問題概要

整数 n と配列 cuts が与えられます。長さ n 単位の木棒があり、両端には 0 から n までの目盛りが付けられています。cuts[i] は棒を切断できる位置を表します。切断はどのような順序でも実行できますが、1回の切断にかかるコストは「その瞬間に切断する木棒の長さ」であり、全体のコストはすべての切断コストの合計です。合計コストが最小になるように切断順序を選んだときの最小コストを求めます。

具体例

n = 7、cuts = [5, 1, 4, 3] の場合、答えは 16 になります。たとえば切断順序を [3, 5, 1, 4] とすると、以下のように進みます。

• まず長さ 7 の棒を位置 3 で切断 → コスト 7(残りは長さ 3 と 4 の2本)
• 次に位置 5 で切断 → 長さ 4 の部分を切るためコスト 4(累計 11)
• 次に位置 1 で切断 → 長さ 3 の部分を切るためコスト 3(累計 14)
• 最後に位置 4 で切断 → 長さ 2 の部分を切るためコスト 2(累計 16)

これよりも良い切断順序は存在しないため、最小合計コストは 16 となります。

アプローチ:区間動的計画法(区間DP)

この問題は、典型的な区間DPとして定式化できます。cost[i][j] を「区間 [cuts[i], cuts[j]] 内にあるすべての切断位置を実行するときの最小コスト」と定義します。各区間について最初に行う切断位置 s を全通り試し、区間を左右に分割した結果と組み合わせることで最適解が得られます。

手順は以下のとおりです。

• cuts を昇順にソートし、先頭に 0、末尾に n を挿入したリストを作成する
• m := リストの要素数とする
• cost := m × m の二次元リストを 0 で初期化する
• k を 2 から m-1 まで動かし、区間の長さごとに計算する
  • i を 0 から m-1 まで動かし、j := i + k とする
  • j ≥ m の場合は次の反復へ進む
  • cost[i][j] = (cuts[j] − cuts[i]) + min(cost[i][s] + cost[s][j])(s は i+1 以上 j 未満の範囲)
• 最後に cost[0][m-1] を返す

Python実装例

以下の実装で理解を深めましょう。

def solve(n, cuts):
    cuts = [0] + sorted(cuts) + [n]
    m = len(cuts)
    cost = [[0] * m for _ in range(m)]

    for k in range(2, m):
        for i in range(m):
            j = i + k
            if j >= m:
                continue
            cost[i][j] = (cuts[j] - cuts[i]) + min(
                cost[i][s] + cost[s][j] for s in range(i + 1, j)
            )

    return cost[0][m - 1]


n = 7
cuts = [5, 1, 4, 3]
print(solve(n, cuts))

入力

7, [5,1,4,3]

出力

16

計算量

• 時間計算量:O(m³)(m は cuts の要素数 + 2。区間の組み合わせ O(m²) × 各区間の分割点探索 O(m))
• 空間計算量:O(m²)(DPテーブルの保存に必要)

まとめ

切断位置をソートして両端の 0 と n を追加することで、問題は「隣接する切断位置の間の区間」を単位とする区間DPに帰着します。各区間で最初の切断位置を全探索することで、無数に存在する切断順序の中から最適なものを効率的に見つけられます。貪欲法では最適解が保証されないため、このようなDPによるアプローチが重要になります。