貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita

はじめに ついこないだの AtCoder 上のコンテストで出題された問題 AtCoder Beginner Contest 099 C 問題 - Strange Bank が、初心者向けの 300 点問題としては史上最難ではないかということで話題沸騰になりました。 何も考えずに DP (動的計画法) した 辺の長さが 1 の DAG なので BFS でも DP でも Dijkstra でも OK 個数制限なしナップサック問題を復習しないと 全探索 + Greedy でやった といった色んな声が飛び交いました。動的計画法アルゴリズムの設計法などを具体的に学べるすごく教育的な問題だと思ったので、上記の事柄をまとめて整理することを試みます。それにしてもこの問題はコイン両替問題の 1 パターンとして位置付けられますが、色んな取り組み方ができますね。 ABC 099 C - Strange Bank