Quiz
https://atcoder.jp/contests/abc099/tasks/abc099_c
Submit
https://atcoder.jp/contests/abc099/submissions/5118558
感想
- けんちょんさんの記事 https://qiita.com/drken/items/ace3142967c4f01d42e9
- を読んでいたらStrange Bankを「配るDP」で解いてみたくなった
- その結果、配る感をしっかり理解できた気がする
今回の問題でいう配るDP解法
- 使えるコインのリストを作る (1, 6, 36, ..., 9, 81, ...)
- dp[i] : i円を作る時の最小コイン枚数
- dp[0] = 0
- dp[i]のiを1から順に埋めていく
dp[0] = 0; FOR(i, 0, 100000){ for(ll c : coins){ ll num = dp[i] + 1; dp[i+c] = min(dp[i+c], num); } }