পাইথন প্রোগ্রাম - দেওয়া কয়েন দিয়ে n টাকা পাওয়ার উপায়ের সংখ্যা বের করুন

মনে করুন (1, 2, 5, 10) ডিনোমিনেশনवाले কয়েন দেওয়া আছে। এই ডিনোমিনেশন ব্যবহার করে n টাকা পাওয়ার কত প্রকার উপায় আছে তা বের করতে হবে। count নামে একটি ৪ উপাদানের অ্যারে আছে, যেখানে count[0] = ১ টাকার কয়েনের সংখ্যা, count[1] = ২ টাকার কয়েনের সংখ্যা ইত্যাদি।

ইনপুট n = 27, count = [8,4,3,2] হলে আউটপুট হবে ১৮। কিছু সম্ভাব্য কম্বিনেশন:

10*2 + 5*1 + 2*1 = 27
10*2 + 2*3 + 1*1 = 27
10*1 + 5*3 + 2*1 = 27
10*1 + 5*1 + 4*2 + 4*1 = 27

সমাধানের ধাপসমূহ (ডাইনামিক প্রোগ্রামিং):

denom := [1,2,5,10]
A := (n+1) আকারের অ্যারে ০ দিয়ে ভরা
B := A-র কপি
i = 0 থেকে min(count[0], n) পর্যন্ত: A[i] := 1
i = 1 থেকে 3 পর্যন্ত:
- j = 0 থেকে count[i] পর্যন্ত:
  - k = 0 থেকে n+1 - j*denom[i] পর্যন্ত: B[k + j*denom[i]] += A[k]
- j = 0 থেকে n পর্যন্ত: A[j] := B[j], B[j] := 0
A[n] ফেরত দিন

উদাহরণ

বাস্তবায়ন:

denom = [1,2,5,10]

def solve(n, count):
    A = [0 for _ in range(n+1)]
    B = list(A)
    for i in range(min(count[0], n) + 1):
        A[i] = 1
    for i in range(1, 4):
        for j in range(0, count[i] + 1):
            for k in range(n + 1 - j * denom[i]):
                B[k + j * denom[i]] += A[k]
        for j in range(0, n + 1):
            A[j] = B[j]
            B[j] = 0
    return A[n]

n = 27
count = [8,4,3,2]
print(solve(n, count))

ইনপুট

27, [8,4,3,2]