Para üstü: en az madeni para

Problem

Farklı değerlerde madeni paralar (coins) ve bir hedef tutar (amount) veriliyor. Her paradan sınırsız sayıda kullanabilirsin. Tutarı tam olarak oluşturmak için gereken en az madeni para sayısını döndür. Mümkün değilse -1.

coins = [1, 3, 4], amount = 6
Açgözlü: 4 + 1 + 1 -> 3 para
En iyi:  3 + 3     -> 2 para
Çıktı: 2

coins = [4, 6], amount = 7   -> -1   (çift paralarla tek sayı yapılamaz)
coins = [5],    amount = 0   -> 0

Netleştirme soruları

• Para değerleri pozitif mi, birbirinden farklı mı? (Evet.)
• amount = 0 için cevap 0 mı? (Evet; hiç para kullanmamak.)
• amount ne kadar büyük olabilir? (DP dizisi amount + 1 boyutunda olacak; 10^9 olsaydı bu yaklaşım çalışmazdı.)
• Kombinasyonun kendisi mi, sayı mı isteniyor?
• Para sistemi "kanonik" mi (Türk lirası gibi)? (Kanonikse açgözlü çalışır; genel durumda çalışmaz.)

İpuçları

Yaklaşım

Açgözlü neden yanlış: Kanonik olmayan para sistemlerinde büyük parayı almak ileride daha kötü bir duruma kilitler. Karşı örnek: [1, 3, 4], 6.

Kaba özyineleme: f(x) = 1 + min f(x - c); dallanma |coins|, derinlik amount'a kadar: üstel.

DP (seçilen çözüm): Durum minCoins[x] = x tutarı için en az para. Optimal alt yapı: x'in en iyi çözümünden son parayı çıkarırsan kalan, x - c'nin en iyi çözümüdür (değilse daha iyisini koyup x'i iyileştirebilirdin). Alt problemler örtüşür, bu yüzden tabulation. Bu, sınırsız sırt çantası (unbounded knapsack) ailesinin minimum versiyonudur.

BFS bakışı: 0'dan başlayıp her adımda bir para ekleyen BFS, tutara ilk ulaştığı katmanda en az para sayısını verir (her kenar ağırlığı 1). Aynı karmaşıklıktadır; testlerde bağımsız referans olarak kullanıldı. Bu bakış açısını söylemek, adayın problemleri farklı modellerle görebildiğini gösterir.

Döngü sırası: Dış döngü tutar, iç döngü para. Bu soruda (minimum sayı) döngüleri ters çevirmek de doğru sonuç verir. Ama "kaç farklı kombinasyon" sorusunda (Coin Change II) sıra kritiktir: para dışta olmalıdır, yoksa 1+2 ile 2+1 ayrı sayılır.

Java çözümü

import java.util.Arrays;

public final class CoinChange {

    public int coinChange(int[] coins, int amount) {
        int impossible = amount + 1;                      // hiçbir çözüm amount'tan fazla madeni para kullanmaz
        int[] minCoins = new int[amount + 1];             // minCoins[x]: x tutarı için en az para sayısı
        Arrays.fill(minCoins, impossible);
        minCoins[0] = 0;

        for (int x = 1; x <= amount; x++) {
            for (int coin : coins) {
                if (coin <= x && minCoins[x - coin] + 1 < minCoins[x]) {
                    minCoins[x] = minCoins[x - coin] + 1; // son atılan para 'coin' ise
                }
            }
        }
        return minCoins[amount] == impossible ? -1 : minCoins[amount];
    }
}

Sentinel olarak amount + 1 seçilmesinin nedeni: hiçbir geçerli çözüm amount'tan fazla para kullanamaz (en küçük para en az 1). Böylece minCoins[x - coin] + 1 asla taşmaz ve ulaşılamazlık tek bir karşılaştırmayla kontrol edilir. Integer.MAX_VALUE kullanıp + 1 yapmak negatif sayıya taşar ve "en iyi" sonuç gibi görünür.

Karmaşıklık

• Zaman: O(amount · |coins|).
• Bellek: O(amount).
• Not: Bu "pseudo-polynomial" bir zamandır: girdinin bit uzunluğuna göre değil, amount'un değerine göre büyür. amount = 10^9 ise pratik değildir.

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• [1, 3, 4], 6: 2 (açgözlünün yanıldığı durum).
• [4, 6], 7: -1.
• amount = 0: 0.
• Tek para tam eşleşme [7], 7: 1.
• Büyük klasik girdi [186, 419, 83, 408], 6249: 20.
• [Integer.MAX_VALUE, 1], 1: 1. coin <= x kontrolü sayesinde dev para dizinin dışına taşmaya yol açmıyor.
• 3.000 rastgele girdi (1-4 para, değerler 1-20, tutar 0-149) BFS referansıyla karşılaştırıldı.

Mülakatçı için

Coin Change, DP'nin "gerçek" ilk sorusudur. Gözlemle: aday açgözlüyle başlarsa karşı örneği kendi bulabiliyor mu? Durum ve geçişi kodlamadan önce cümleyle ifade ediyor mu? Sentinel ve taşma konusunu nasıl ele alıyor? -1 dönüşünü unutuyor mu?

İpucu zamanlaması: Açgözlü çözümü yazan adaya doğrudan "yanlış" deme; [1, 3, 4] ve 6 ile dry run iste. Rekürans 5 dakikada gelmezse ikinci ipucunu ver. Memoization ile yukarıdan aşağı çözen adayı eksik sayma, ama amount = 10^4 için özyineleme derinliğini sor.

Takip sorusu 1: Tutarı oluşturan kaç farklı kombinasyon var? Beklenen: ways[x] += ways[x - c], dış döngü paralar üzerinde; sıra ters olursa permütasyon sayılır (LeetCode 518).

Takip sorusu 2: Kullanılan paraları da döndür. Beklenen: her x için hangi paranın en iyi sonucu verdiğini lastCoin[x] dizisinde tutmak, sonra amount'tan geriye x -= lastCoin[x] ile yürümek.

Takip sorusu 3: Her paradan sınırlı adet var (kasadaki gerçek bozuk para). Beklenen: sınırlı sırt çantası; adetleri ikili parçalara bölmek (1, 2, 4, ...) ya da her para için tutarı ters yönde gezmek. Bir ATM ya da kasa sisteminde ayrıca "ileride üstü verilebilsin diye küçük paraları koru" gibi iş kurallarının algoritmayı değiştireceğini söylemek artı sinyaldir.

Benzer problemler

• Coin Change II (LeetCode 518)
• Perfect Squares (LeetCode 279)
• Minimum Cost For Tickets (LeetCode 983)
• Combination Sum IV (LeetCode 377)
• Climbing Stairs (LeetCode 70)