この問題を題材にして、DP の組み立て方（どういう思考をたどれば、この問題に適したDPの構成を思い付けるか）の例を示します。
答えを知っている方が見ると、まわりくどい・・・と感じるかも知れませんが、あくまで、「まったく答えの見当がつかない・・・・」という状況で、何を手がかりに考察を進めればよいかを示していると思ってください。
「しらみつぶし」を再帰的に記述
文字列の長さが問題のサイズ N に対応しそうな気はしますが、文字列が2つあるので、それぞれの文字列の長さをどのようにして個別に扱えばよいのか、ちょっと悩ましいかも知れません。
DPの本質は、「小さなサイズの問題の答え」を使って、「大きなサイズの問題の答え」を導くという点にありますので、逆に言うと、「大きなサイズの問題」を如何にして「小さなサイズの問題」に帰着させるか、ということを考える必要があります。これは、ある意味、再帰的に問題を解く時の考え方と同じです。
そこで、一旦、DPのことは忘れて、「しらみつぶし」の方法で構わないので、これをどうやって再帰的に解くことができるかを考えてみます。
しらみつぶしで構わないのであれば、たとえば、2つの文字列を s1, s2 とした時に、「s1 のあらゆる部分列」について、同じ部分列が s2 から取れるかをチェックするという方法が考えられます。
「s1 のあらゆる部分列」をどうやって作るかというと、
・先頭の文字 s1[0] を含む場合／含まない場合
・2番目の文字 s1[1] を含む場合／含まない場合
のあらゆる組み合わせを考えることになります。
したがって、この問題を解く関数を solve(s1, s2) とすると、最初の部分はこのようになるはずです。ここでは、solve(s1, s2) は発見された最長の部分文字列そのものを返すものとしています。
def solve(s1, s2): case1 = # s1[0] を含まない場合の答え case2 = # s1[0] を含む場合の答え if len(case1) > len(case2): return case1 else: return case2
case1 と case2 の場合分けが入っていますが、case1 の場合は、簡単に再帰することができます。s1 の先頭の文字は使わない前提なのですから、s1[1:] と s2 について同じ問題を解けばOKです。
def solve(s1, s2): if len(s1) == 0 or len(s2) == 0: return '' case1 = solve(s1[1:], s2) # s1[0] を含まない場合の答え case2 = # s1[0] を含む場合の答え if len(case1) > len(case2): return case1 else: return case2
これを再帰的に呼び出すと、s1 の長さが 1 ずつ小さくなっていくので、最後は 0 （つまり空文字列）になり、この場合の答えは '' （空文字列）とすぐにわかります。（今の段階では、s2 の長さがどの様に減るかはわかりませんが）s2 についても同様に、空文字列の場合はすぐに '' と答えがきまります。
そして次は、s1 の先頭の文字を含む場合ですが、ここでちょっと頭を使う必要があります。何も考えずに solve(s1, s2) を再度呼び出すと、当然ながら、無限ループになります。なんとかして、s1 か s2 のどちらかを 1 文字でも減らしたケースにひもづける必要があります。s1 の先頭文字 s1[0] を使うと言うことは、s2 のどこかに同じ文字があるはずです。仮に、s1[0] == s2[0] だとすればどうでしょう？
はい。この場合は簡単ですね。s1[0] == s2[0] は、一致する部分文字列の先頭の文字として採用することができますので、これらを取り除いて、別途、残りの部分をさがせばOKです。
if s1[0] == s2[0]: case2 = s1[0] + solve(s1[1:], s2[2:])
ちなみに、
s1 = 'abcd' s2 = 'aoooabc'
という場合、
s1 = 'abc-' s2 = 'a----bc'
s1 = 'abc-' s2 = '----abc'
という2種類のマッチのさせ方がありますが、少なくとも、先頭の文字同士をペアにするパターンはかならず存在する点に注意してください。
これで無事に、より小さいサイズの問題に帰着することができました。それでは、s1[0] != s2[0] の場合はどうすればよいのでしょう・・・？
s2[1], s2[2],... をスキャンして、最初に s1[0] == s2[k] となる k を発見する？？？
いえいえ。このようなスキャンループは、当然ながら計算が長くなりますので、再起処理の中でのさらなるループはできる限り避けるべきです。s1[0] != s2[0] ということは、少なくとも、（s1[0] を使うという前提では）s2[0] を使うことはありませんので、これを捨ててしまって、s1 と s2[1:] についての問題を解けば良いのです。
if s1[0] == s2[0]: case2 = s1[0] + solve(s1[1:], s2[1:]) else: case2 = solve(s1, s2[1:])
んんん？？？？ solve(s1, s2[1:]) を実行すれば、必ず、s1[0] を含む場合の解が得られるんでしたっけ？
大丈夫です。仮に、s1[0] を含む解が存在しなかった場合、solve(s1, s2[1:]) が返す結果は、case1 で先に計算した solve(s1[1:], s2) に負ける（もしくは引き分ける）はずです。最後に case1 と case2 を比較する部分で case1 が選ばれるので問題ありません。
というわけで全体をまとめると次の様になります。
def solve(s1, s2): if len(s1) == 0 or len(s2) == 0: return '' case1 = solve(s1[1:], s2) # s1[0] を含まない場合の答え ---- (1) # s1[0] を含む場合の答え if s1[0] == s2[0]: case2 = s1[0] + solve(s1[1:], s2[1:]) # ---- (2) else: case2 = solve(s1, s2[1:]) # ---- (3) if len(case1) > len(case2): return case1 else: return case2
この結果を改めて見直すと、(1) と (3) は対称になっていることに気が付きます。s1[0] を含む場合／含まない場合、という場合分けで考えてきましたが、実は、次の3つの場合を計算して、これらの中でベストなものを選ぶ、という戦略と同等になっていることが分かります。（この3つが論理的にすべての場合を網羅していることは・・・、よく考えるとわかりますよね。）
・s1[0] == s2[0] の場合 ： case1 = s1[0] + solve(s1[1:], s2[1:])
・s1[0] != s2[0] で、s2[0] を使わない場合： case2 = solve(s1, s2[1:])
・s1[0] != s2[0] で、s1[0] を使わない場合： case3 = solve(s1[1:], s2)
サイズが小さいケースに帰着させる方法を理解
上記の結果から、s1, s2 についての問題を解く際は、「それぞれの文字列から１文字取り除いた問題（一方だけ取り除くケース2種類、両方から取り除くケース1種類）」が事前に解けていればよいことが分かります。こう考えると、ちょっとDPっぽい雰囲気になりますよね。
[xxxxx] [xxxxxxxxx]
を解くには、
[-xxxx] [xxxxxxxxx]
[xxxxx] [-xxxxxxxx]
[-xxxx] [-xxxxxxxx]
を先に解いておけばよいのです。
ただこのイメージだと、右から左にデータが増えていくので、ちょっと気持ち悪いです。この方向のループでDPを組み立てても良いのですが、今の場合、文字列の左右は本質ではないので、ちょっと頭を切り替えて、
[xxxx-] [xxxxxxxxx]
[xxxxx] [xxxxxxxxx-]
[xxxx-] [xxxxxxxx-]
の結果を使って、
s1: [xxxxx] s2: [xxxxxxxxx]
が解けないか、あらためて考え直してみましょう。DPの記法を導入して、上の3つの結果（答え）を dp[n1-1][n2]、dp[n1][n2-1]、dp[n1-1][n2-1] として、これらを使って最後の問題の答え dp[n1][n2] を求めるわけです。n1 = len(s1), n2 = len(s2) だとしてください。
前項の最後に説明した、3つの論理的な区分で考えてみましょう。
・最後の文字が一致する場合 s1[n1] == s2[n2]
この場合、最後の文字をペアに採用して、残りの前の部分について問題を解けばOKです。
if s[n1] == s2[n2]: case1 = dp[n1-1][n2-2] + s1[n1]
・最後の文字が一致しない場合 s1[n1] != s2[n2]
この場合、s1[n1] と s2[n2] のどちらか一方は、絶対に解に含まれないはずですので、dp[n1-1][n2] と dp[n1][n2-1] のベストな方を採用すればOKです。
case1 = '' case2 = '' if s[n1] == s2[n2]: case1 = dp[n1-1][n2-2] + s1[n1] else: tmp1 = dp[n1-1][n2] tmp2 = dp[n1][n2-1] if len(tmp1) > len(tmp2): case2 = tmp1 else: case2 = tmp2 if len(case1) > len(case2): dp[n1][n2] = case1 else: dp[n1][n2] = case2
おー。これで、DP の遷移処理が実装できてしまいました。あとは、n1 と n2 のループを回しながら、dp[n1][n2] を順番に埋めていけばよいはずです。
DPで実装
dp[n1][n2] の計算に必要な情報は、dp[n-1][n2-1]、dp[n-1][n2]、dp[n1][n2-1] ですので、n1 と n2 のループを回す順序は特に気を使う必要はないでしょう。
for n1 in range(0, len(s1)): for n2 in range(0, len(s2)):
なのですが・・・・ここでちょっとだけマイナーな修正をさせてください。今、s1、s2 は Python の文字列型なので、n1=0、および、n2=0 の場合に、s1[n1]、s2[n2] は1文字目を表します。しかしながら、DP のテンプレート的には、n1=0、n2=0 は、速攻で答えがわかる「端っこ」のケース（再帰的な実装で言えば、s1 = '', s2 ='' にあたるケース）に対応して欲しいところです。これ以降は、s1 と s2 の1文字目には「端っこ」を示す記号 '*' が埋め込まれており、s[n1]、s[n2] は文字通りに、n1 文字目、n2 文字目に対応することにします。
この約束にすれば、n1 = 0、もしくは、n2=0 のケースはもれなく dp[0][n2] = dp[n1][0] = '' と決まります。
というわけで出来上がったのが次のコードになります。最終的な答えは、それぞれの文字列をフルに使った場合の結果として、dp[len(s1)-1][len(s2)-1] から読み出すことができます。
s1 = '*' + s1 # 「端っこ」の記号を追加 s2 = '*' + s2 # 「端っこ」の記号を追加 dp = [[''] * (len(s2)) for _ in range(len(s1))] for n1 in range(0, len(s1)): for n2 in range(0, len(s2)): if n1 == 0 or n2 == 0: # 「端っこ」の場合 dp[n1][n2] = '' continue case1 = '' case2 = '' if s1[n1] == s2[n2]: case1 = dp[n1-1][n2-1] + s1[n1] else: tmp1 = dp[n1-1][n2] tmp2 = dp[n1][n2-1] if len(tmp1) > len(tmp2): case2 = tmp1 else: case2 = tmp2 if len(case1) > len(case2): dp[n1][n2] = case1 else: dp[n1][n2] = case2 print(dp[len(s1)-1][len(s2)-1])
さっそく提出してみましょう。
うむむむ。３割ぐらいのケースで、実行時間オーバー（もしくは、メモリ容量オーバー）になっています。厳しいですね。。。
文字列長から文字列を再構成する
DPのアルゴリズムとしては、上記の ケースで基本的には問題ありません。恐らくは、Python で文字列の操作をしまくっているので、時間がかかっていると思われます。C言語で実装してみるとか、いろいろ試してみましたが・・・結論としては、
・文字列そのものではなく、文字列長を dp[n1][n2] に記録する
・最後に文字列長を記録した2次元リスト dp[ ][ ] から部分文字列を再構築する
という対処が必要でした。2つめの文字列長から文字列を再構成する、というところは、ちょっとアルゴリズムっぽいので、ここだけ追加で説明しておきます。
まず、n1 = len(s1) - 1, n2 = len(s2) - 1 として、最後の dp[n1][n2] の値を見ると、s1、s2 全体を使った場合の最長部分文字列数がわかります。
で、この上 dp[n1-1][n2] は s1 の最後の文字を削った場合、もしくは、左の dp[n1][n2-1] は s2 の最後の文字を削った場合を表します。
仮に、どちらかの文字が部分文字列に使われていたとすれば、上か左のどちらかの値は減少するはずです。上が減っていると仮定しましょう。この場合、s1 の最後の文字をピックアップした上で、（上ではなく）左へ進んでいきます。やがて、マッチする s2 の文字にたどりつきます。つまり s1[n1] == s2[n2] が成り立ちます。ここにたどり着いたら、ここからさらに左上に移動した上で、同じ手続きを再開します。これは、今マッチした文字以降を s1 と s2 の両方から切り捨てて、残りの部分について探索を再開することになります。
なお、上も左もどちらも、dp の値が減少しない場合は、s1 と s2 のどちらの最後の文字を削っても構わないことを意味しますので、上でも左でも好きな方向に移動して、また同じ手続きを再開してください。移動をすすめていって、dp[n1][n2] = 0 にたどり着いたらそこで終了です。
言葉で説明するとややこしいですが、コードにするとこんな感じですね。
n1 = len(s1) - 1 n2 = len(s2) - 1 result = '' while dp[n1][n2] > 0: if dp[n1-1][n2] < dp[n1][n2]: result = s1[n1] + result while s1[n1] != s2[n2]: n2 -= 1 n1 -= 1 n2 -= 1 elif dp[n1][n2-1] < dp[n1][n2]: result = s2[n2] + result while s1[n1] != s2[n2]: n1 -= 1 n1 -= 1 n2 -= 1 else: n1 -= 1 print(result)
ここまでの修正をした上で提出すると、無事に全問正解となります。
