Chương trình Python bài toán đổi tiền (Coin Change)

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho N đồng tiền, muốn đổi tiền sao cho cóupply vô hạn mỗi giá trị trong S. Cần hiển thị số cách đổi tiền (không quan tâm thứ tự).

Dùng quy hoạch động để giảm độ phức tạp thời gian.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# dynamic approach
def count(S, m, n):
    # base case
    table = [[0 for x in range(m)] for x in range(n+1)]
    # n=0
    for i in range(m):
        table[0][i] = 1
    # điền bottom-up
    for i in range(1, n+1):
        for j in range(m):
            # solutions including S[j]
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
            # solutions excluding S[j]
            y = table[i][j-1] if j >= 1 else 0
            # total
            table[i][j] = x + y
    return table[n][m-1]

# main
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print("Số cách đổi tiền:", count(arr, m, n))

Kết quả

Số cách đổi tiền: 6

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python bài toán đổi tiền.