ferinの競プロ帳

競プロについてのメモ

2017-03-29から1日間の記事一覧

DPL_4 B Coin Combination Problem II

Coin Combination Problem II | Aizu Online JudgeN

DPL_1 E Edit Distance (Levenshtein Distance)

dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。 各文字列に対する操作についてDPの遷移を考えると 挿入 dp[i][j] = dp[i][j-1] + 1 削除 dp[i][j] = dp[i-1][j] + 1 置換 dp[i][j] = dp[i-1][j-1] + 1 となります。さらに…