競プロ弱者のDP コイン問題

1/5のAtCoderのDPまとめコンテスト以来、DPの解説をよく見かけます。

そこで、私もDP解説を書いてみます。

C++では書ける自信がなかったのでpythonで競プロを始める方が増えているので言語はpythonで解説します。

理解できたDPがこれしかないのでまずは簡単なコイン問題から始めます。

例題１

3円、5円、8円のコインが1枚ずつある。0枚以上のコインを組み合わせ、11円ちょうど支払うことができるか？

解法

①全部のコインの合計額+1の大きさのリストを用意する。(例題1の場合は3+5+8+1=17)

　この時、全ての要素は0にしておく。

リストの中身はこの状態　

コインのリストも作る

②リストの0番～16番までを支払いたい金額とし、支払えない場合を0、支払える場合を0で表現する。

コインを1枚も選ばなければ0円を作れる。よってリストの0番を1にする。

リストの中身はこの状態　

③1枚目のコインを使う場合と使わない場合を考える。

④同様に残りのコインも処理をする。
処理は、リストを逆順に見ていって、dp[16-j]==1であればdp[16-j+coin[i]]=1とする

1枚目のコインを使わなかった場合は0円、使った場合は3円なので、

1枚目のコインの処理が終わった段階(i=0が終わった状態)はこの状態

2枚目のコインの処理が終わった段階

3枚目の処理が終われば

となる。

⑤問題は、11円をちょうど支払えるかだったので、dp[11]を見ると、1なので支払い可能

⑥ところで、③でリストを逆順で見たのは、リストを0番から順に見ると、1枚目のコイン(3円)では、dp[0]==1なのでdp[3]を1にして・・

dp[1],dp[2],dp[3]と見て、dp[3]が1になっているので、dp[6]も1に、同様にdp[9]も1にしてしまう。3円は1枚しかないのにこれはまずい。リストを逆順に見ていればこれを防げる。

わかりにくい説明に最後までお付き合いいただきありがとうございました。
次回は「コイン何枚で〇円を作れるか」のコイン問題を解説します。

AtCoderレートを上げるとともに、解説能力も上げたいと思いますので、次回はもう少しわかりやすく書きます。