PAST009H LCSと同様. \(s,t\) の最後の文字 \(s_{i}, t_{j}\) を使うかどうかで場合分け. \(s_{[0,i)}, t_{[0,j)}\) に対する答えを \(dp_{i,j}\) とおく. \(s_{i} \neq t_{j}\) のとき:使った方が良い. 言い換えると,使う最適な選び方が存在する. このとき\(dp_{i,j} + 1\) . \(s_{i} = t_{j}\)のとき: どちらかは使えない. \(s_{i}\) を使わない場合: \(dp_{i,j+1}\). \(t_{j}\) を使わない場合: \(dp_{i+1,j}\). 初期化 …