動的計画法part3(最長共通部分列問題)

２つの文字列t, sが与えられる。
これら２つの共通部分文字列の長さの最大値を求めよ。
共通部分文字列とは、互いに共有する文字列であり、連続で一致している必要は無いが、
順序は等しくなければならない。

s = "abcd"
t = "becd"

LCS = 3
(以後LCS(Longest Common Subsequence)は、最長共通部分長を指す)

・動的計画法
漸化式を作る。
(1)i番目とj番目が等しいとき
文字列探索において、tのi番目とsのj番目が等しいとき、
LCS(t(i-1),s(j-1))に1をプラスすればよい。

例：
t = ABCDEA
s = ABDECA

i = 6, j = 6のとき。
i=5, j=5のときのLCS = "ABDE" = 4 に +1をすればよい。

(2)i番目とj番目が等しくないとき、
LCS(t(i),s(j-1)) or LCS(t(i-1),s(j))のどちらか大きい方を採用する。

例：
t = ABCDE
s = ACD

i = 5, j = 3の場合、
sのj-1番目から取ってくると、最長共通部分"ACD"より一つ少ない値を取得することになる。
そのため、どちらか大きい方を取得する必要がある。

よって、漸化式は、
\[dp[i][j] =dp[i-1][j-1] + 1 (t(i) == s(j)の場合) \]
\[dp[i][j] = max(dp[i][j-1], dp[i-1][j]) (それ以外) \]

dp[0][x]、dp[x][0]は、それぞれ空の文字列と比較している為、
出力は「０」としてよい。
よって、dp[0][0],dp[0][1]....dp[1][0],dp[1][1]....
と網羅的に解くことができる。