Leetcode 322 Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

Input: coins = [1], amount = 0
Output: 0

Input: coins = [1], amount = 1
Output: 1

• Bu soruda bize bir kaç demir para (coins = [1,2,5]) ve bir sayı veriliyor.Ve demir en az kaç demir para kullanarak bu sayıyı bulabileceğimiz soruluyor.Eğer bu demir paralardan istenen sayı elde edilemiyorsa -1 dönmemiz isteniyor.
• Soru güzel bir soru.Dinamik programlama tekniği ile çözebiliriz.
• Bizden 7 elde etmemiz istensin.Ve [1,2,5] demir paraları verilmiş olsun.7 tane 1 kullanabiliriz.Yada 3 tane 1 ve 1 tane 1 ile 4 parada 7 elde edebiliriz.Yasa sadece 5 ve 2 kullanarak sadece 2 parada 7 elde ederiz.Peki bunu nasıl bulacağız.
• İlk olarak tüm istenen değerler için kaç demir para kullanılacağını yüksek değerler girerek oluştururuz.Çünkü karşılaştırma yaparak hangisi daha az demir para kullanıyorsa onu bırakacağız.
• Burada yakalamamız gereken desen şu, her istenen değeri elimizdeki paralarla en düşük olacak şekilde elde etmek.
• 0’dan 7’ye kadar minimum paraları nasıl elde edebiliriz bakalım.
• Elimizde sadece [1] olsun
• Para sayısı 0 1 2 3 4 5 6 7
• İstenen değer 0 1 2 3 4 5 6 7
• Burada 2 ile oluşturmaya çalışacağız.0 ve 1 değişmez.Ama 2 ye geldiğimizde 2 tane 1 ile de oluşturabiliriz yada sadece 2 ile de oluşturabiliriz.Karar vermemiz gerekir. numOfCoins[amount] = min(numOfCoins[amount],1+numOfCoins[amount-c])
• Elimizde [1,2] olsun
• Para sayısı 0 1 1 2 2 3 3 4
• İstenen değer 0 1 2 3 4 5 6 7
• Burada 5 ile sayılar nasıl değişti görelim.0,1,2,3,4 hepsi 5 ten küçük olduğu için değişmedi.İstenen değer 5 ise ve elimizde 5lik bir para var ise min(numOfCoins[5],1+numOfCoins[5-5]) yani min(3(bir önceki durumda 3 tane para ile 5 oluşturmuştuk),1 +numOfCoins[0])
• Elimizde [1,2,5] olsun
• Para sayısı 0 1 1 2 2 1 2 2
• İstenen değer 0 1 2 3 4 5 6 7
• Bu şekilde 0’dan bizden istenen değer(amount) kadar tüm listeyi doldururuz.Sonrada istenen değeri döneriz.
• Eğer elimizdeki değer programın başında oluşturduğumuz yüksek değer ise bu durumda elimizdeki paralardan bu sayıyı oluşturamamışızdır -1 döneriz.

    def coinChange(self, coins: List[int], amount: int) -> int:
        numOfCoins = [amount + 1] * (amount + 1)
        numOfCoins [0] = 0

        for c in coins:
            for amount in range(len(numOfCoins)):
                if c <=amount:
                    numOfCoins[amount] = min(numOfCoins[amount],1+numOfCoins[amount-c])
                    
        if numOfCoins[amount] != amount + 1:
            return numOfCoins[amount]
        else:
            return -1