http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2092
以下の2つ解法がある
AABCEAG
という文字列でDFSを考えてみる。まず、
A ABCEA G
と分ける。AとGは異なるので、右端のGを取り除いた文字列と左端のAを取り除いた文字列でdfsをすることになる。よって返す値は
return max( dfs( AABCEA ), dfs( ABCEAG ) )
となり解は２つのdfsの最大値に限定出来る。ここで左のdfs
AABCEA
について考える。以下のように
A ABCE A
と分けると、左右のAは一致しているので返す値は
return dfs( ABCE ) + 2
である。また、右のdfsにおいては左端と右端が異なるのではじめと同様に2つの文字列に分割してdfsする。
後は再帰の終了条件を指定してやれば終わり
入力の文字列sに対し、t = rev(s) を考える。sとtで最長共通部分列問題として解くと解が求まる。蟻本の内容をそのまま使うと、解はdp[n][n]となる。
