পাইথনে ভারতীয় মুদ্রা দিয়ে n টাকা তৈরির উপায়ের সংখ্যা বের করা

সীমিত সংখ্যক কয়েন আছে: ₹1, ₹2, ₹5, ₹10। এই কয়েনগুলো যোগ করে মোট ₹n তৈরির কতটি উপায় আছে তা বের করতে হবে। count অ্যারে সাইজ ৪, যেখানে count[0] = ₹1 কয়েনের সংখ্যা, count[1] = ₹2, count[2] = ₹5, count[3] = ₹10।

উদাহরণ

ইনপুট: n = 25, count = [7, 3, 2, 2]

আউটপুট: 9

সমাধান পদ্ধতি

1. denom := [1, 2, 5, 10]
2. A এবং B নামের দুটি অ্যারে সাইজ n+1 ০ দিয়ে ইনিশিয়ালাইজ করুন।
3. i = 0 থেকে min(count[0], n) পর্যন্ত: A[i] := 1
4. 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
5. A[n] রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

denom = [1, 2, 5, 10]

def solve(n, count):
    A = [0] * (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(count[i] + 1):
            for k in range(n + 1 - j * denom[i]):
                B[k + j * denom[i]] += A[k]
        for j in range(n + 1):
            A[j] = B[j]
            B[j] = 0
    return A[n]

# টেস্ট
n = 25
count = [7, 3, 2, 2]
print(solve(n, count))  # আউটপুট: 9

ইনপুট

25, [7,3,2,2]

আউটপুট

9