ALDS1_10_B: Matrix Chain Multiplication (続き3)
テキストのコードをまんまPythonに移したもの
全然短い
捉え方は違うけど結果的にやってることは似たようなもの・・・(たぶん)
二次元配列への入れ方が45度傾いてたり
行列の覚え方が効率良くなってたりするけど
def count(ms):
n = len(ms)
p = [0] * (n + 1)
for i in range(n):
p[i] = ms[i][0]
p[i + 1] = ms[i][1]
m = [[None] * (n + 1) for _ in irange(n)]
for i in irange(1, n):
m[i][i] = 0
for l in irange(2, n):
for i in irange(1, n - l + 1):
j = i + l - 1
m[i][j] = maxsize
for k in irange(i, j - 1):
m[i][j] = min(
m[i][j],
m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
)
return m[1][n]