Coin Change

いくつかの異なる額面の硬貨を無制限に使えるとして、できるだけ少ない枚数でちょうどの金額を支払いたいとします。

金額に収まる中で最も大きい硬貨を取るのがよさそうに思えますが、うまくいかないことがあります。硬貨が [1, 3, 4] で金額が 6 の場合、最初に最大の硬貨を使うと 4 + 1 + 1 となり、3枚必要です。一方、3 + 3 なら2枚で済みます。

より確実なのは、小さな金額から答えを積み上げていく方法です。fewest[t] を、合計が t になる最少枚数とします。0 を支払うのに硬貨は必要ありません。それ以外の t では、最後に使う硬貨の額面を c とすると、その前に残っている金額は t - c なので、次のようになります。

fewest[t] = 1 + t 以下のすべての硬貨 c についての fewest[t - c] の最小値。

[1, 3, 4] の場合、fewest[3] = 1 であり、fewest[6] = 1 + fewest[3] = 2 です。どの硬貨を使っても到達可能な金額にならない場合、t はまったく支払えません。

coinChangeという名前の関数を作成してください。この関数は、互いに異なるコインの額面のリストであるcoinsと整数のamountを受け取り、合計がちょうどamountになる最少のコイン枚数を返します。各額面のコインは何度でも使用できます。金額を作れない場合は-1を返し、amountが0の場合は0を返してください。

たとえば、coins = [2, 5, 10]、amount = 27の場合は4（10 + 10 + 5 + 2）を返し、coins = [4, 6]、amount = 7の場合は-1を返します。

制約: 1 <= coins.length <= 12、1 <= coins[i] <= 10^4、すべての値は互いに異なる、0 <= amount <= 10^4。