概要
概要
最長共通部分列は、2 つの列に共通して現れる順序付き要素列の最長長を求めます。DP テーブルが典型です。
動的計画法・再帰 / LCS（最長共通部分列）
最長共通部分列は、2 つの列に共通して現れる順序付き要素列の最長長を求めます。DP テーブルが典型です。
目次
このページでわかること
概要
最長共通部分列は、2 つの列に共通して現れる順序付き要素列の最長長を求めます。DP テーブルが典型です。
考え方
if s[i] == t[j]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(top, left)要点
O(nm)
O(nm)
文字列 DP
長さまたは列
補足
左上 + 1 を使います。
上と左の大きい方を取ります。
表の見た目が近いので並べると良いです。
動きで確認
ここでは「状態が何か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。