今日は引き続きDPの勉強を。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
このページの「４．二次元ナップサックDP」以降を勉強しましたが
なかなか理解が追いつかなかったので色々なページを引っ張りながら自分なりに解釈しました。
まずLCS問題。
二つの文字列が与えられて，最長の共通部分列を見つける問題(Longest Common Subsequence) です。
最初意味が分かりませんでしたが、下の解説URLの説明を見て「なるほど・・・」と納得。
簡単に考えるには、文字列SとTを並べて表を作ると良いのですね。
例えば、S: abcde T:acbefdが与えられた場合には、２つの文字列を縦と横にとって以下の表が作れます。
この表ではSの各文字が先頭から何番目かをiで表し、Tの各文字が先頭から何番目かをｊで表しています。
表のマス目に入るのはdp[i][j]、つまりSのi文字目までとTのj文字目まででのLCSの長さだとします。
まずは地道に考えてみます。
例えばdp[1][1]の場合は、Sの1文字目まではa, Tの1文字目までもaなのでLCSの長さは1, よってdp[1][1]=1になります。
dp[1][2]の場合は、Sの1文字目まではa, Tの2文字目まではacですが、この場合LCSの長さは1, よってdp[1][2]=1ですね。
そんな風に考えていくとこの表が埋まって・・・
こうなります。
ここで、どういう規則で各dp[i][j]が決まっていくのか？を考えるために、赤の四角で囲った部分に着目してみます。
この赤枠の中は今埋まっていますが、左下のdp[5][6]を周りの3つの数字を手がかりだけに考えられないか検討してみます。
つまりこんなイメージ。
| dp[4][5]=2 | dp[5][5]=3 |
| dp[4][6]=3 | dp[5][6]=? |
さて、まずdp[4][5]からdp[5][6]に視点を動かしたとき・・・
dp[4][5]というのは、Sの4番目までとTの5番目までのLCSの長さなので、
SもTも一文字分増やした場合、その文字同士が一致していれば（つまりS[i]=T[j]なら）LCSは当たり前に1文字分長くなります。
逆に一致していなければ増えません。そのままです。
ということは
dp[5][6] = dp[4][5] + 1 (S[i]==T[j]のとき)
dp[4][5] （S[i] != T[j]のとき）
今回だとS[5]=eとT[6]=dは一致しないので dp[5][6] = dp[4][5] = 2。これがdp[4][5]から考えた時の値（①）。
ではdp[5][5]からdp[5][6]に視点を動かした場合は？
一方の文字が増えたところでLCSが長くなることはないので、dp[5][6] = dp[5][5] = 3。これがdp[5][5]から考えた時の値（②）。
最後dp[4][6]からdp[5][6]に視点を動かした場合も上と同様なので、dp[5][6] = dp[4][6] = 3。これがdp[4][6]から考えた時の値（③）。
というふうに、dp[5][6]は①～③という導き方の違いによる3つの答え候補が出てきます。
この中で最大値のものが、dp[5][6]の本当の値になるはずです（だってLCSは最長の共通部分ですからね・・・）。
うーん、こんなことを解釈するだけでも時間がかかるので本当によくない。
話は戻ってDPの記事にある編集距離（レーベンシュタイン距離）についてもやっぱり理解が追いつかず、以下のURLを参考にしました。
なんでもそうなのですが、
プログラミング勉強してると「頭いいなぁ・・・」「なんでこんなの思いつくんだ・・・」っていうものばっかりに遭遇します。
知の洗練されたものに触れている感じ。
シンプルで美しい構造や処理は尊敬しかないです。すごいや。
土曜日にはBeginner Contest108に参加しました。
これで2回目の大会参加ですが、前よりもA問題とB問題が速く解けました。
でも結局目標としていたC問題は解けず。
難しく考えすぎて駄目でした。解説見てがっくり。
日曜日に実装しました。
あとは引き続きBITの学習（もうなんか実装すればいいんじゃないかって気になってきた）と、
深さ優先探索の勉強をしました。
深さ優先探索についてはなんもわからん。
解けないので以下のURLを解読したい。
http://mmxsrup.hatenablog.com/entry/2016/10/23/135920
これもそう。解けない。
解読して書くぞという気持ち。
https://beta.atcoder.jp/contests/arc031/submissions/2976193
