外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

N - Cat and cat

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、siooisi、tau0529、trueryob

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

編集距離DPという典型を用います。

文字列SaS_aの先頭ii文字と、文字列SbS_bの先頭jj文字を一致させるための操作コストをdp[i][j]dp[i][j]とすると、dp[∣Sa∣][∣Sb∣]dp[|S_a|][|S_b|]は、O(∣Sa∣∣Sb∣)O(|S_a||S_b|)で漸化的に求めることができます。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。