Sequence Matching
dp[i][j]: A_1, ..., A_i と B_1, ..., B_j で考えたときの答え
初期値はかんたん
dp[i][0] = i (A_1 から A_i まで消す)
dp[0][j] = j (B_1 から B_j まで消す)
遷移を考える
このときの注意点として
A_1 〜 A_i と B_1 〜 B_j のペアの作り方は決まってる (固定されている) とみなす
というのがある
つまり dp[6][8] を考えるときに A_6 と B_2 が等しいかなどは気にしなくてよい
(そのようなケースは dp[6][2] で考慮するため)
(i, j) ← (i - 1, j): A_i を消して、A がひとつ短い問題に帰着
コスト 1
(i, j) ← (i, j - 1): B_j を消して、B がひとつ短い問題に帰着
コスト 1
(i, j) ← (i - 1, j - 1): A_i, B_j を残して、A, B がひとつ短い問題に帰着
同じ値ならコスト 0, 違うなら 1
dp[n][m] が元の問題での答え