競技プログラミングやアルゴリズムの勉強をしていると、最長共通部分列（LCS）の問題に直面することがよくあります。LCSの問題は動的計画法（DP）を使用して解くことが多いですが、その立式に関して疑問を感じることもあります。この記事では、LCSのDPの立式がどのように導かれるのかを、具体的な例を交えて解説します。
1. 最長共通部分列（LCS）とは
最長共通部分列（LCS）とは、2つの文字列の中で順番を変えずに共通する部分列のうち、最も長いものを指します。例えば、文字列「ABCDEF」と「AEBDF」について、最長共通部分列は「ABDF」になります。
LCSの問題を解くために動的計画法（DP）を使用する方法が一般的で、計算量を効率よく抑えることができます。
2. DPの二次元配列の立式
LCSを解くためには、2つの文字列の各文字を比較しながら、共通部分列をどのように構築していくかを考えます。このとき、DPを用いて、文字列の各位置までの最長共通部分列の長さを記録していきます。
具体的には、2つの文字列の長さをそれぞれn, mとし、(n+1)×(m+1)の二次元テーブルdpを用意します。dp[i][j]は、文字列s_nの先頭からi番目までと、文字列s_mの先頭からj番目までの最長共通部分列の長さを表します。
3. DPの遷移式について
DPの遷移式を理解するために、具体的にどのように遷移するかを見てみましょう。
3.1. dp[n][m] = dp[n-1][m-1] + 1 の理由
もし文字列s_nのn番目の文字と、文字列s_mのm番目の文字が一致する場合、最長共通部分列の長さは、dp[n-1][m-1]に1を足したものになります。なぜなら、s_nのn番目とs_mのm番目の文字を追加することで、共通部分列が1つ長くなるからです。
例えば、「AEBDF」のような文字列で、「A」や「B」が一致する場合、その前までの最長共通部分列に新たにこの一致を加えることになります。
3.2. dp[n][m] = max(dp[n][m-1], dp[n-1][m]) の理由
一方で、文字列s_nのn番目の文字と、文字列s_mのm番目の文字が一致しない場合、最長共通部分列は、次の2つのうちどちらか大きい方になります。
- dp[n-1][m]（文字列s_nのn番目を無視して進める）
- dp[n][m-1]（文字列s_mのm番目を無視して進める）
これにより、文字列s_nとs_mの一致しない部分で最適な部分列を選ぶことができます。
4. 実際の処理の流れを追う
実際の処理を追うことで、立式がどのように導かれるのかを理解できます。まず、dp[0][0]は0で初期化し、その後、文字列s_nとs_mの各文字を比較し、上記の遷移式に従ってテーブルを更新していきます。
例えば、文字列「ABCDEF」と「AEBDF」を例に取ると、dpテーブルは次のように埋められていきます。各セルには、最長共通部分列の長さが順番に格納されます。
5. まとめ
LCSの問題は、動的計画法（DP）を用いることで効率的に解くことができます。dp[n][m]の遷移式は、文字列s_nとs_mの一致する文字を見つけた場合と、一致しない場合の2パターンで定義されており、それぞれのケースで適切にテーブルを更新していきます。
このように、最長共通部分列の問題を解くためには、DPを使って計算量を削減しながら、逐次的に共通部分列を構築していくことが重要です。
コメント