ALDS1_10_C: Longest Common Subsequence (続き)

やっぱりアルゴリズムの問題？

解説を読んだ
自分のコードに近い感じに読み替えるとこうか

• 文字列1の先頭の文字と文字列2の先頭の文字が等しければ、文字列1の2文字目以降と文字列2の2文字目以降の最長共通部分文字列の長さ+1
• 異なっていれば、文字列1の2文字目以降と文字列2の最長共通部分文字列の長さと、文字列1と文字列2の2文字目以降の最長共通部分文字列の長さの長い方

これでいいのか
なんかややこしくしてたな

1文字ずつ引数が変わっていくからこの方がメモ化が効きそうな気がする

def lcs(s1, s2):

    @lru_cache()
    def rec(i1, i2):
        nonlocal s1, l1, s2, l2

        if i1 == l1 or i2 == l2:
            return 0

        if s1[i1] == s2[i2]:
            return rec(i1 + 1, i2 + 1) + 1
        else:
            return max(rec(i1 + 1, i2),
                       rec(i1, i2 + 1))

    l1 = len(s1)
    l2 = len(s2)
    return rec(0, 0)

自前テストではひと桁くらい速くなった
でもジャッジは通らない
TLEになったデータは20回lcsを実行するんだけど
そのなかの1回分のデータでもまったく終わる気配なし

本のコードをそのままpythonにしてみた
こういうのもメモ化なんだろうか

def lcs(s1, s2):

    l1 = len(s1)
    l2 = len(s2)
    c = [[0] * (l2 + 1) for _ in range(l1 + 1)]

    maxl = 0
    s1 = " " + s1
    s2 = " " + s2

    for i1 in range(1, l1 + 1):
        for i2 in range(1, l2 + 1):
            if s1[i1] == s2[i2]:
                c[i1][i2] = c[i1 - 1][i2 - 1] + 1
            else:
                c[i1][i2] = max(c[i1 - 1][i2],
                                c[i1][i2 - 1])
            maxl = max(maxl, c[i1][i2])

    return maxl

1回のテストなら1秒ちょっと
うーんでも20回やると・・・
やっぱTLEじゃないすかー