ALDS1_10_C: Longest Common Subsequence (続き2)
やっぱTLEじゃないすかー
ほかのひとのコードを見てみる
本のアルゴリズムで通ってるやつはないっぽい
そして(細かくは見てないけど)けっこういろんな解き方があるっぽい
Webで探してみるとみんな動的計画法のサンプルとして解いてて
同じ解き方
もうちょっと自分で考えてみよう
・・・と思って考えてみたけど再帰以外思いつかないなあ
あらためてほかのひとのコードを見てみると
Heesanさんという人のコードが、2次元配列を使ってないだけで
ほぼ本と同様の動的計画法であることに気づいた
見てくれを前回の普通にメモ化したコードに寄せて書き直してみるとこう
配列で必要なのは直前の行(列?)だけなので、前行だけコピーして
覚えるようになってるけれど、考え方は同じ
def lcs2(s1, s2):
l1 = len(s1)
l2 = len(s2)
c = [0] * (l2 + 1)
for i1 in range(l1):
cprev = c[:]
for i2 in range(l2):
if s1[i1] == s2[i2]:
c[i2 + 1] = cprev[i2] + 1
elif c[i2 + 1] < c[i2]:
c[i2 + 1] = c[i2]
return c[-1]
これでずいぶんと速くなってジャッジを通る
2次元配列と1次元配列でけっこうアクセス速度が変わるってことかな
あと、毎回maxlと比較してたのは実は不要っぽい
c[l1][l2]が最大に決まってるので
maxlの比較をやめるだけでもけっこう速くなる
(でもジャッジが通るほどではない)
上のコードに合わせて、普通にメモ化したコードの添字ずらしたり
maxlの比較をやめたりしたコードはこう
やっぱり同じ
def lcs(s1, s2):
l1 = len(s1)
l2 = len(s2)
c = [[0] * (l2 + 1) for _ in range(l1 + 1)]
for i1 in range(l1):
for i2 in range(l2):
if s1[i1] == s2[i2]:
c[i1 + 1][i2 + 1] = c[i1][i2] + 1
else:
c[i1 + 1][i2 + 1] = max(c[i1][i2 + 1],
c[i1 + 1][i2])
return c[l1][l2]
ただし、+1が増えたせいかただmaxlの比較をやめた版より少し遅い
ループの中ってやっぱり影響大きいんだなあ(こなみ
これくらいで!