日記

のみろぐ

主に競プロ日記です

2019-01-01から1日間の記事一覧

コイン問題

考察 状態変数を考える dp[i円の最小枚数]でいけそう。50000円がMaxだから制約的にも行けそう 次に遷移を考える dp[i] ← dp[i-c[j]] + 1みたいな感じで行けそう。計算量も$O(nm)$で余裕がある。最大で$106$ステップだし 解法 dp[i円の最小枚数]という状態を…