DP: Coin Change in Hack Rank
問題
N枚の異なるコインと支払いたい金額moneyが与えれる。与えられたコインはそれぞれ無限に使える時、与えられたコインを使って合計金額がmoneyとなるような支払い方法の通り数を求める問題。
解法
動的計画法と用いることで計算量O(N*money)で解くことができる。
コインは配列で与えれる。配列のインデックスをi
と置く。i
番目から最後の要素までのコインを使って、これまでの金額の総和がsum
となるような支払い方法の通り数を求める関数をwayToPay(int i, int sum)
と置く。すると
watToPay(i, sum) = Σ(i ≦ k < n) wayToPay(k, sum + coins[k])
と書くことができる。後はこれを再帰を用いて解いてあげれば良い。また、処理中にi
とsum
の組合せは何度も登場するので、その値を配列に保存し、一度登場した組合せは保存した値を再利用することで計算量を大幅にカットすることができる。
重複した組合せを数えないために、先程の式の右辺の第一引数ではk
を指定することにも注意。