kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

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次元配列作るところもスッキリしないんだけど
ここはどう書くのが定番なのかなあ