Coin Change
Farklı madeni para değerlerinden oluşan coins listesini ve hedef amount değerini alırsın. Her madeni para değerini istediğin kadar kullanabilirsin. Değerleri toplamda tam olarak amount eden en az sayıda madeni parayı döndür; hiçbir madeni para kombinasyonu bu değere ulaşamıyorsa -1 döndür. 0 tutar için 0 madeni para gerekir.
Fonksiyon
- coinsinteger-array
- farklı madeni para değerleri, her biri istenildiği kadar kullanılabilir
- amountinteger
- ödenecek toplam tutarı tam olarak
- Döndürürinteger
- gereken en az madeni para sayısı veya tutar oluşturulamıyorsa -1
Kısıtlar
1 ≤ coins.length ≤ 121 ≤ coins[i] ≤ 1040 ≤ amount ≤ 104- Tüm madeni para değerleri farklıdır.
Örnekler
- Girdi
- coins = [2, 5, 10]amount = 27
- Çıktı
- 4
- Açıklama
- 10 + 10 + 5 + 2, dört madeni parayla 27 eder. Üç madeni para yetmez: 27 tek sayıdır, bu yüzden tam olarak bir tane 5'lik gerekir ve diğer iki madeni para en fazla 20 eder; 22'ye ulaşamaz.
- Girdi
- coins = [4, 6]amount = 7
- Çıktı
- -1
- Açıklama
- Her iki madeni para değeri de çifttir, bu nedenle oluşturabileceğin her toplam çifttir. 7 tektir, dolayısıyla cevap -1'dir.
- Girdi
- coins = [3, 7]amount = 0
- Çıktı
- 0
- Açıklama
- 0 ödemek hiç bozuk para gerektirmez; bu yüzden bozuk paraların değerleri ne olursa olsun yanıt 0'dır.
Ek soru
En az sayıda coin'i bulmak yerine, amount değerine ulaşan kaç farklı coin kombinasyonu olduğunu sayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Sığan en büyük madeni parayı her zaman almak, her zaman en az sayıda madeni parayı vermez. Bunu
[1, 3, 4]madeni paraları ve6tutarıyla deneyin.t'den küçük her miktar için gereken en az madeni para sayısını zaten bildiğini varsayalım.tmiktarına bir madeni para daha ekleyerek hangi daha küçük miktarlardan ulaşabilirsin?fewest[0..amount]tablosunu0'dan başlayarak doldur:fewest[0] = 0ve herfewest[t],c <= tkoşulunu sağlayan madeni paralar arasındaki en iyifewest[t - c]değerinden bir fazladır. Ulaşılamayan miktarları,amount + 1gibi gerçek tüm yanıtlardan büyük bir değerle işaretle ve sonunda bu değeri-1'e dönüştür.
Çözüm
Sığan en büyük madeni parayı almak işe yaramaz: 1, 3 ve 4 değerindeki madeni paralarla 6 tutarı 4 + 1 + 1 şeklinde ödenirken, 3 + 3 iki madeni para gerektirir. Bir tutar için gereken en az madeni para sayısı yalnızca daha küçük tutarlar için gereken en az madeni para sayısına bağlıdır; bu nedenle 0'dan amount değerine kadar her tutarı bir kez çözersin.
Özyineleme kullanarak her kombinasyonu deneyin
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Ödediğin son madeni paranın değeri c ise, ondan önceki madeni paralar remaining - c tutarını mümkün olduğunca ucuza öder. Bu yüzden fewest(remaining), sığan her madeni para için en iyi fewest(remaining - c) değerinden bir fazladır. Bu yöntem, toplamı aşmayan her madeni para dizisini dener, dolayısıyla en iyisini gözden kaçıramaz.
Aynı tutarları tekrar tekrar çözer. 2, 5 ve 10 değerindeki madeni paralarla, 27 tutarı 10 + 2, 2 + 10, 5 + 5 + 2 ve daha fazla sıralamadan sonra 15'e ulaşır ve her seferinde 15'i baştan hesaplar. Çağrı sayısı, tutarla birlikte üstel olarak artar.
Algoritma
fewest(remaining)yardımcı fonksiyonunu yazın; bu fonksiyon,remainingiçin gereken en az madeni para sayısını, uygun hiçbir seçenek yoksa -1 değerini döndürür.remaining0 ise 0 döndürün.remainingdeğerinden büyük olmayan her madeni para için, o madeni parayla ödeme yaptıktan sonra geriye kalana yardımcı fonksiyonu çağırın.- -1 olmayan en küçük sonucu ve ödediğiniz madeni para için 1'i tutun.
- Bu sayıyı döndürün veya her madeni para sonuçsuz kaldıysa -1 döndürün. Yanıt
fewest(amount)şeklindedir.
def coinChange(coins, amount):
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
return best
return fewest(amount)Önbellekleme ile özyineleme
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Özyineleme yalnızca 0 ile amount arasındaki miktarları sorar. Her yanıtı ilk hesapladığında bir dizide sakla ve aynı miktar yeniden karşıya çıktığında saklanan değeri döndür. Her miktar, madeni paralar üzerinde bir döngüyle bir kez çözülür: O(amount × coins) işlem.
Çağrılar yine de ödenen her madeni para için bir seviye iç içe geçer. Değeri 1 olan bir madeni parayla bu, 10^4 seviyeye kadar çıkabilir; bu da birçok dilde varsayılan çağrı yığınının izin verdiğinden fazladır.
Algoritma
- 0'dan
amount'a kadar her miktar için yer ayıran ve henüz hesaplanmadığını belirten bir işaret tutanmemodizisini oluştur. fewest(remaining)içinde, 0 için 0 döndür; zaten bir yanıt içeriyorsamemo[remaining]değerini döndür.- Aksi hâlde, basit özyinelemede olduğu gibi sığan her madeni parayı dene ve en küçük sonuca 1 ekle.
- Döndürmeden önce sonucu, -1 de dahil olmak üzere,
memo[remaining]içine kaydet. fewest(amount)değerini döndür.
def coinChange(coins, amount):
# memo[r] holds the answer for r once it is worked out; None means not yet
memo = [None] * (amount + 1)
def fewest(remaining):
# The fewest coins that add up to remaining, or -1 if no mix does
if remaining == 0:
return 0
if memo[remaining] is not None:
return memo[remaining]
best = -1
for coin in coins:
if coin <= remaining:
rest = fewest(remaining - coin)
if rest != -1 and (best == -1 or rest + 1 < best):
best = rest + 1
memo[remaining] = best
return best
return fewest(amount)Tutarlar üzerinde alttan üste dinamik programlama
Sezgi
fewest tablosunu 0'dan başlayarak doldur. Bir t toplamına ulaştığında, daha küçük her toplam çözüme kavuşmuştur; bu nedenle fewest[t], sığan madeni paralar c için fewest[t-c] değerlerinin en küçüğünden bir fazladır.
Madeni paraların hiçbir kombinasyonunun ulaşamadığı toplamlar, amount + 1 işaretçisini taşır. Her madeni para en az 1 değerinde olduğundan, gerçek bir yanıt hiçbir zaman amount madeni paradan fazlasını kullanmaz ve işaretçi tüm karşılaştırmaları kaybeder. Döngü özyinelemenin yerini alır; bu nedenle çağrı yığınının derinliği hiçbir zaman önem taşımaz.
Algoritma
amount + 1girdisi olan ve tümü işaretçiamount + 1değerine ayarlanmışfewestdizisini oluşturun vefewest[0]değerini 0 yapın.- 1'den
amountdeğerine kadar her toplamtiçin,c ≤ tkoşulunu sağlayan her madeni parayıcinceleyin. fewest[t-c] + 1değerifewest[t]değerinden küçükse, bu değerifewest[t]içine kaydedin.- Döngüden sonra,
fewest[amount]hâlâ işaretçi değerini taşıyorsa -1, aksi hâldefewest[amount]değerini döndürün.
def coinChange(coins, amount):
impossible = amount + 1
fewest = [0] + [impossible] * amount
for total in range(1, amount + 1):
for coin in coins:
if coin <= total and fewest[total - coin] + 1 < fewest[total]:
fewest[total] = fewest[total - coin] + 1
return fewest[amount] if fewest[amount] != impossible else -1
Tuzaklar ve uç durumlar
- Önce en büyük madeni parayı kullanmak. 3 ve 5 değerinde madeni paralarla ve 9 tutarındaki miktarla 5 ve 3 öder, 1'de takılıp -1 döndürür; oysa 3 + 3 + 3 işe yarar.
- İşaretleyici olarak en büyük tam sayıyı kullanmak. Buna 1 eklemek taşmaya ve negatif bir sayıya yol açar; bu sayı da her karşılaştırmayı kazanır.
amount + 1kullanın. - Çıkmaz bir yola 1 eklemek. -1 döndüren bir dal, ödediğiniz madeni para değeriyle toplandığında 0 eder ve her karşılaştırmayı kazanır. -1 sonuçlarını atlayın.
amountdüzeyinde özyinelemeli çağrı yapmak. Değeri 1 olan bir madeni para ve10^4miktarıyla Python varsayılan 1000 düzey sınırına ulaşır; JavaScript, Dart, Ruby ve R'de de yığın tükenir.- Madeni para değeri
t'den büyükken tablonun başlangıcından öncefewest[t-c]değerini okumak.
Sıkça sorulan sorular3
Coin Change için açgözlü yaklaşım neden başarısız olur?
Sığan en büyük madeni parayı almak yalnızca çoğu gerçek para birimi gibi bazı madeni para sistemlerinde güvenlidir. 1, 3 ve 4 değerindeki madeni paralarla 6’yı iki yerine üç madeni parayla öder; 3 ve 5 değerindeki madeni paralarla ise 9’u hiç ödeyemez. Dinamik programlama tüm seçenekleri karşılaştırır; dolayısıyla hiçbir madeni para sistemi onu yanıltamaz.
Coin Change'in zaman karmaşıklığı nedir?
Dinamik programlama çözümü O(amount × coins) zaman ve O(amount) alan kullanır: her miktar için bir tablo girdisi ve her girdi için kontrol edilen her madeni para. Önbellekleme olmadan kullanılan basit özyineleme, miktara göre üstel zaman alır.
Coin Change için yukarıdan aşağıya yaklaşım mı, yoksa aşağıdan yukarıya yaklaşım mı daha iyi?
İkisi de aynı O(amount × coins) işi yapar. Yukarıdan aşağı özyineleme, miktar kadar derine iç içe geçebilir ve bu da birçok dilde 10^4 için çağrı yığınının taşmasına neden olur. Aşağıdan yukarıya yaklaşım tabloyu bir döngüyle doldurur; bu nedenle derinlik sınırı yoktur ve mülakatta daha güvenli bir seçenektir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def coinChange(coins, amount):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
coins = [2, 5, 10] amount = 27
Beklenen Çıktı
4