Coin Change

Birkaç farklı değerde sınırsız sayıda madeni paran var ve tam tutarı mümkün olduğunca az madeni para kullanarak ödemek istiyorsun.

Sığan en büyük madeni parayı almak kulağa doğru geliyor, ancak başarısız olabilir. [1, 3, 4] madeni paraları ve 6 tutarı için, önce en büyük madeni parayı almak 4 + 1 + 1 sonucunu verir; bu üç madeni para demektir. Oysa 3 + 3 için yalnızca iki madeni para gerekir.

Daha güvenli bir yol, yanıtı küçük tutarlardan başlayarak oluşturmaktır. fewest[t], toplamı t olan en az madeni para sayısı olsun. 0 ödemek hiç madeni para gerektirmez. Diğer her t için kullandığın son madeni paranın değeri c olsun; ondan önce kalan tutar t - c olur, dolayısıyla

fewest[t] = 1 + the smallest fewest[t - c], t'den büyük olmayan her madeni para c için.

[1, 3, 4] için: fewest[3] = 1 ve fewest[6] = 1 + fewest[3] = 2. Hiçbir madeni para ulaşılabilir bir tutara götürmüyorsa t hiç ödenemez.

coinChange adlı, coins adlı farklı madeni para değerlerinden oluşan bir listeyi ve amount adlı bir tam sayıyı alan ve toplamı tam olarak amount eden en az sayıda madeni parayı döndüren bir işlev yazın. Her madeni para değerini istediğiniz kadar kullanabilirsiniz. Tutar oluşturulamıyorsa -1, amount 0 olduğunda ise 0 döndürün.

Örneğin, coins = [2, 5, 10] ve amount = 27 için 4 döner (10 + 10 + 5 + 2); coins = [4, 6] ve amount = 7 içinse -1 döner.

Kısıtlamalar: 1 <= coins.length <= 12, 1 <= coins[i] <= 10^4, tüm değerler farklıdır, 0 <= amount <= 10^4.