Leetcode 322 找零錢

題目描述

題目給予不同面額與目的總金額，編寫函數求得最少數量的硬幣

輸出

• 硬幣數量
• 都無法組成的話輸出-1

解題

抽象化

• 給定數組與目標值，求出最少組成。
• 貪婪法是否適用？不可行
• 動態規劃是否適用？
• 切鋼條？

貪婪法 (不可行)

1. 每次抓最大
2. 最大不行嘗試以次優的解法

注: 貪婪法不一定能做到最佳解，因此會得到錯誤結果。

動態規劃

• 分而治之
  • 一個函數能夠找到最小組成
  • 函數選取把剩下的子問題交給下一個函數
  • 如果函數能夠批配，則回傳數量，否則回傳-1
• 列表法: 把重複問題解記下來

程式碼

測資

[1,2,5]
11
[1]
0
[0]
0
[1]
11
[2]
3
[1,2,4,8,16,32,64,128]
338
[186,419,83,408]
6249
[83,186,408,419]
6249
[1, 0]
12
[1]
100000
[1,2,4,8,16,32,64,128, 256, 512, 1024]
11340