配るDP 〜Strange Bank〜

Quiz

https://atcoder.jp/contests/abc099/tasks/abc099_c

Submit

https://atcoder.jp/contests/abc099/submissions/5118558

感想

今回の問題でいう配る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);
        }
    }

f:id:peroon:20190425191143j:plain