SRM 458 Div1 Medium New Coins

商品の価格のリストが与えられ、それらを全て１つずつ買うときに必要な枚数の合計を最小にするようにコインを発行する。ただし全てのコインの額面は、それより小さいコインの整数倍になっていなければならない。
このとき全ての品物を１つずつ買うのに必要なコインの枚数を求めよ。

各所での解説の通りにメモ化再帰でやりました。

あるいは次のようなボトムアップでも多分可。
akの額面のコインを発行しているときの、ak以上のコインを使う部分での支払い方の最適解がわかっている時、
akの約数ak-1についてコインを発行した時の、ak-1以上のコインを使う部分の最適解がわかる。
（価格のakの剰余をrとするとΣr/ak-1）
これをak=最も高い商品の価格から下げて行けばいい。