区間DPは短い区間から
左右の区間を合体する問題では、区間 [l,r) を状態にします。分割点をすべて試して最小値を選びます。
言語：Python / 計算量：O(N³)、メモリ O(N²)
考え方
- dp[l][r] を区間の最適値と定義。
- 長さ1を初期化。
- 区間長を増やし、l<k<r の分割を試します。
具体例
重さ[1,2,3]を隣同士だけ合体。先に1+2なら費用3、その後6で合計9。先に2+3なら5+6=11です。
実装
a=[1,2,3];n=len(a);s=[0]
for x in a:s.append(s[-1]+x)
dp=[[0]*(n+1) for _ in range(n)]
for length in range(2,n+1):
for l in range(n-length+1):
r=l+length
dp[l][r]=min(dp[l][k]+dp[k][r] for k in range(l+1,r))+s[r]-s[l]
print(dp[0][n])注意する条件
分割点を試す分があるため O(N³)。最適化には追加条件が必要で、常に二分探索できるわけではありません。
確認問題
[2,3] を合体する最小費用は？
解答と理由
5
合体は1回だけで、重さの和5を支払います。
実装課題
N と正整数配列 A。隣接する2塊を合体し、その和を費用として払う。1塊にする最小総費用。1≤N≤100、A_i≤10^6。
入力:
3
1 2 3
出力:
9参考実装
n=int(input());a=list(map(int,input().split()));s=[0]
for x in a:s.append(s[-1]+x)
dp=[[0]*(n+1) for _ in range(n)]
for length in range(2,n+1):
for l in range(n-length+1):
r=l+length
dp[l][r]=min(dp[l][k]+dp[k][r] for k in range(l+1,r))+s[r]-s[l]
print(dp[0][n])