DP: Coin Change in Hack Rank

問題

N枚の異なるコインと支払いたい金額moneyが与えれる。与えられたコインはそれぞれ無限に使える時、与えられたコインを使って合計金額がmoneyとなるような支払い方法の通り数を求める問題。

www.hackerrank.com

解法

動的計画法と用いることで計算量O(N*money)で解くことができる。


コインは配列で与えれる。配列のインデックスをiと置く。i番目から最後の要素までのコインを使って、これまでの金額の総和がsumとなるような支払い方法の通り数を求める関数をwayToPay(int i, int sum)と置く。すると

watToPay(i, sum) = Σ(i ≦ k < n) wayToPay(k, sum + coins[k])

と書くことができる。後はこれを再帰を用いて解いてあげれば良い。また、処理中にisumの組合せは何度も登場するので、その値を配列に保存し、一度登場した組合せは保存した値を再利用することで計算量を大幅にカットすることができる。

重複した組合せを数えないために、先程の式の右辺の第一引数ではkを指定することにも注意。

ソースコード