硬币最小数量

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

思路

动态规划，变成小问题递归求解

如果有硬币[1, 2, 5], 总量11

从上到下的动态规划：

选取0个1， 递归[2, 5], 11；选取一个1，递归[2, 5], 10; 或者选2个1，递归[2, 5], 9.......

递归结束条件是当前只有一个硬币的时候，判断总量是否能整除硬币面值，如果能返回数量，不然返回-1或者其他“不正常”的值。

需要注意的是，从上到下的方式很多时候可能是重复调用，比如上面的例子，选取一个1，一个2，递归[5], 8; 和选取三个1，0个2，递归[5], 8是一样的。为了避免重复调用，可以使用一个map记录调用的参数信息，如果调用过，直接返回结果。这里递归的硬币就可以使用当前硬币在数组中的位置参数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))