Counting Change Combinations

計算出所有找零的可能組合數量

此題連結
https://www.codewars.com/kata/541af676b589989aed0009e7

題目說明

假設要找回6元 零錢的種類有1, 2, 5元這三種
那可能組合就是
1, 1, 1, 1, 1, 1
2, 2, 2
2, 2, 1, 1
2, 1, 1, 1, 1
5, 1

Ans: 共5種可能

解法說明：

解法有很多種，像我第一次看到這題目就是用超暴力的遞迴來解，有解出來但timeout不給過就想很久，最後直接去問google大神，有很多演算法以下是我學到的

假設要找回10元 零錢的種類有2, 3, 5元這三種
那我們就先創出array index 0~10，

公式 if (coin >= arr[index] ) arr[index] += arr[index-coin]

   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ←要找回的金額
2  1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1  ←2元要找回的金額的可能性
3  1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2  ←2&3元要找回金額的可能性
5  1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4  

如果有其他解法歡迎分享◟( •ω• )◞