AOJ Matrix Chain Multiplication

内容

• AOJ "Matrix Chain Multiplication"を pythonでといた。
• 下のやつの区間DP編 qiita.com

問題

• 複数の行列の積を計算するときに、どの順番で計算すると、scalarの乗算が少なくなるのか? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_B&lang=ja

• e.g. A:(1,2),B:(2,3),C:(3,4)の3つの二次元行列があった時に、

  • (A*B)*Cだと 1*2*3+1*3*4=18
  • A*(B*C)だと、2*3*4+1*2*4=32
• この例では、(A*B)*Cの18が答えとなる。

考えたこと

• DPする。

  ポイント

• pythonで再帰したくなので 再起なしで書く。
  • 区間の幅を小さい方から、計算していく。

    実装

N = int(input())
M = [list(map(int, input().split())) for _ in range(N)]


# DP[l][r]=>[l,r)について、答え
DP = [[float("inf")]*(N+1) for _ in range(N)]

for i in range(N):
    DP[i][i] = 0  # 区間じゃない
    DP[i][i+1] = 0  # 要素が一つなので、掛け算にならない->0

for wid in range(2, N+1):  # 区間の幅
    for l in range(N):  # 区間の左端
        r = l+wid  # 右端(区間に含まれない)
        if r > N:  # はみ出てる
            continue

        if wid == 2:
            DP[l][r] = min(DP[l][r], DP[l][r-1]+M[l][0]*M[l][1]*M[l+1][1])
        else:
            for mid in range(l, r):  # [l,r)のなかで、どこを真ん中にするか
                DP[l][r] = min(DP[l][r], DP[l][mid]+DP[mid]
                               [r]+M[l][0]*M[mid][0]*M[r-1][1])
print(DP[0][-1])  # [0,N+1)が答え

終わりに