Số cách đổi tiền n đồng bằng các mệnh giá Việt Nam (1,2,5,10) có giới hạn số lượng trong Python

Cho số lượng hạn chế của các mệnh giá 1, 2, 5, 10 (mảng count kích thước 4). Tìm số cách ghép thành tổng n đồng.

Ví dụ: n=25, count=[7,3,2,2] → kết quả 9.

Giải thuật

• Dùng quy hoạch động với hai mảng A, B kích thước n+1.
• Khởi tạo A[i]=1 cho i từ 0 đến min(count[0], n).
• Với mỗi mệnh giá i=1..3 (2,5,10):
  • Với số lượng j từ 0 đến count[i]:
    • Cập nhật B[k + j*denom[i]] += A[k] cho k phù hợp.
  • Sao chép B sang A, đặt B về 0.
• Trả về A[n].

Ví dụ mã Python

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))  # Output: 9

Đầu vào

25, [7,3,2,2]

Đầu ra

9