ALDS1_10_B: Matrix Chain Multiplication (続き2)
項が1つの積から始めて、2つ、3つ・・・と順番に求めていくことは
できそうだな
def irange(start, stop=None):
if stop:
return range(start, stop + 1)
else:
return range(start + 1)
def count(m):
lm = len(m)
if lm == 1:
return m[0], 0
cache = [[None] * (lm + 1) for _ in irange(lm)]
for i in range(lm):
cache[1][i + 1] = (m[i], 0)
for n in irange(2, lm):
for i in irange(1, lm - n + 1):
min_count = maxsize
min_result = (0, 0)
for j in irange(1, n - 1):
m1, c1 = cache[j][i]
m2, c2 = cache[n - j][i + j]
m3, c3 = result_2(m1, m2), count_2(m1, m2)
c = c1 + c2 + c3
if c < min_count:
min_count = c
min_result = m3
cache[n][i] = (min_result, min_count)
return min_result, min_count
添字を考えるところで頭が死にそうになったけど
書ききってみたらあっさりAC
行列がひとつだけのときの処理を考え落としてたのは内緒だ
1オリジンの配列がどうにも使いづらいので
閉区間を作るirangeという関数を作ってみた
とはいうものの最初の要素がムダになってる気持ち悪さはある
といっても毎回添字から1引くのもやだし
あと2次元配列作るところもスッキリしないんだけど
ここはどう書くのが定番なのかなあ