題目連結:
題目大意:
給定一個正整數N(N ≦ 5),接下來有N個數字,代表N個硬幣面額。再來有一個數字P,表示要找零的金額(硬幣面額和金額都是不超過100的正整數)。
求所有找零的方法,格式詳見範例輸出。並以字典序由小到大輸出。
範例輸入:
3
1 5 10
17
範例輸出:
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)
註:括號裡第一個數字代表第一個面額,第二數字代表第二個硬幣面額,以此類推。因此,面額輸入順序會影響答案。
解題思維:
窮舉第一種硬幣可能的數量,然後對每個可能遞迴到第二種硬幣可能的數量(記得減掉第一種硬幣的金額),以此類推。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。