E - Sequence Matching Editorial by QCFium


dp[\(i\)][\(j\)] \(= A\) が先頭 \(i\) 文字だけで、\(B\) が先頭 \(j\) 文字だけだった場合の答え

として動的計画法を使います。
\(i = 0\) または \(j = 0\) のときの dp[\(i\)][\(j\)] の値は自明です。
\(i \neq 0\) かつ \(j \neq 0\) のときの dp[\(i\)][\(j\)] の値を考えると、\(A_i\)\(B_j\) は両方列の最後なので、 \(A_i, B_j\) の少なくとも一方を消すか、\(A_i, B_j\) を最終的な列で同じ位置に来るように残すしかないことが分かります。
よってdp[\(i\)][\(j\)] の値は以下の中で一番小さいものです

  • dp[\(i - 1\)][\(j\)] \( + 1\) (\(A_i\) を消すことにするとき)
  • dp[\(i\)][\(j - 1\)] \( + 1\) (\(B_j\) を消すことにするとき)
  • dp[\(i - 1\)][\(j - 1\)] \(+ (A_i \neq B_j \) なら \(1\)、そうでなければ \(0)\) (\(A_i\)\(B_j\) を、最終的に同じ位置になるように残すことにするとき)

posted:
last update: