ABC185 E - Sequence Matching (500)

LCSっぽいので同じようにDPで考えてみる

$ dp[i][j] で$ A_iと$ B_jまでで条件を満たす様にするための最小コストとする

$ dp[0][0] は$ A_0 \ne B_0なら1

$ dp[0][i] (i \gt 0) は$ dp[0][i-1] の末尾に文字を追加してそれを消すか、$ A_0 = B_iなら$ i文字目より前を全て消すかなので、

$ dp[0][i-1] + 1 と$ i + (A_0 \ne B_i)の小さい方が入る

$ dp[i][0] も同様

$ dp[i][j] は以下のとおり

$ A_i = B_j の場合、$ dp[i][j] = dp[i-1[j-1]

後ろの追加した文字は同じ文字のためコストがかからない

それ以外の場合、$ dp[i][j] = \min(dp[i-1][j] - 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

AとBのどちらかだけ末尾に文字を追加してそれを消す、または両方に文字を追加して異なる文字というコストを払う

$ dp[n-1][m-1] が求める値

DPがボトルネックで$ O(NM)