Description
Given the list of coins of distinct denominations and total amount of money. Output the minimum number of coins required to make up that amount. Output -1 if that money cannot be made up using given coins. You may assume that there are infinite numbers of coins of each type.
Input
The first line contains 'T' denoting the number of test cases. Then follows description of test cases. Each cases begins with the two space separated integers 'n' and 'amount' denoting the total number of distinct coins and total amount of money respectively. The second line contains N space-separated integers A1, A2, ..., AN denoting the values of coins.
Output
Print the minimum number of coins required to make up that amount or return -1 if it is impossible to make that amount using given coins.
Sample Input
2
3 11
1 2 5
2 7
2 6
Sample Output
3
-1
思路
動(dòng)態(tài)規(guī)劃毫玖，變成小問(wèn)題遞歸求解
如果有硬幣[1, 2, 5], 總量11
從上到下的動(dòng)態(tài)規(guī)劃：
選取0個(gè)1拜英， 遞歸[2, 5], 11板熊；選取一個(gè)1舵揭，遞歸[2, 5], 10; 或者選2個(gè)1，遞歸[2, 5], 9.......
遞歸結(jié)束條件是當(dāng)前只有一個(gè)硬幣的時(shí)候肛跌，判斷總量是否能整除硬幣面值忌怎，如果能返回?cái)?shù)量捏鱼，不然返回-1或者其他“不正炽咀悖”的值胁附。
需要注意的是，從上到下的方式很多時(shí)候可能是重復(fù)調(diào)用，比如上面的例子，選取一個(gè)1恭陡，一個(gè)2，遞歸[5], 8; 和選取三個(gè)1弓候，0個(gè)2，遞歸[5], 8是一樣的洗做。為了避免重復(fù)調(diào)用弓叛，可以使用一個(gè)map記錄調(diào)用的參數(shù)信息，如果調(diào)用過(guò)诚纸，直接返回結(jié)果。這里遞歸的硬幣就可以使用當(dāng)前硬幣在數(shù)組中的位置參數(shù)index陈惰。
python
import functools
def solve(coins, amount):
@functools.lru_cache(None)
def dp(i, amount):
if amount == 0:
return 0
if i == 0:
return [float('inf'), amount // coins[0]][amount % coins[0] == 0]
ans = float('inf')
for j in range(amount//coins[i] + 1):
ans = min(ans, j + dp(i-1, amount-coins[i]*j))
return ans
res = dp(len(coins)-1, amount)
return [res, -1][res == float('inf')]
for _ in range(int(input())):
_, amount = map(int, input().split())
coins = list(map(int, input().split()))
print(solve(coins, amount))
