Python Hazır Kodlar 21 | Para Bozdurma Problemi

Bir sayının verilen sayılar ile kaç farklı şekilde bütünleneceğini hesaplayan program,

Örneğin: Sayı = 4 verilen sayılar ise {1,2,3}: Bu {1,2,3} ile kaç farklı 4 sayısı elde edebiliriz.

Cevap 4 farklı çözüm vardır:  {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. 

Matematikte Coin Change (Para Bozdurma) problemi olarak geçen bu programı yazalım.

def count(S, m, n): 
    # n+1 satırlara ihtiyacımız var
    table = [[0 for x in range(m)] for x in range(n+1)] 
  
    # 0. index i dolduralım
    for i in range(m): 
        table[0][i] = 1
  
    # Tablo girişlerini aşağıdan yukarıya doldurma
    for i in range(1, n+1): 
        for j in range(m): 
  
            # S[j] dahil çözüm sayısı
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
  
            # S[j] hariç çözüm sayısı
            y = table[i][j-1] if j >= 1 else 0
  
            # toplam sayım 
            table[i][j] = x + y 
  
    return table[n][m-1] 
  
# Programı Çalıştıralım
arr = [1, 2, 3] 
m = len(arr) 
n = 4
print(count(arr, m, n)) 

Python dersleri için buraya gidebilirsiniz..