Khóa học Python từ Cơ bản đến Nâng cao

Bài 11.1 - Giải bài toán SCoin Change với Python

Trong bài học này, chúng ta sẽ cùng nhau giải một trong những bài toán cổ điển và rất phổ biến trong lập trình: Coin Change Problem - Tìm số đồng xu ít nhất để đạt được một số tiền nhất định.

Đề bài

Cho danh sách các mệnh giá tiền xu và một số tiền cần đổi. Hãy viết hàm tìm số lượng đồng xu ít nhất cần dùng để đổi được đúng số tiền đó. Nếu không thể đổi được, trả về -1.

Ý tưởng

Bài toán này là một ví dụ kinh điển của quy hoạch động (Dynamic Programming).

Ta sẽ dùng một mảng dp, trong đó dp[i] là số lượng đồng xu ít nhất để tạo ra số tiền i.

Code mẫu cơ bản

def coin_change(coins, amount):
    # Khởi tạo mảng dp với giá trị lớn (amount+1)
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # Không cần đồng nào để đổi 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != amount + 1 else -1

Ví dụ minh hoạ

Ví dụ 1:

coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # Kết quả: 3 (5 + 5 + 1)

Giải thích: 3 đồng xu: hai đồng 5 và một đồng 1.

Ví dụ 2:

coins = [2]
amount = 3
print(coin_change(coins, amount))  # Kết quả: -1

Giải thích: Không có cách nào để tạo thành 3 chỉ với đồng 2.

Ví dụ 3:

coins = [1]
amount = 0
print(coin_change(coins, amount))  # Kết quả: 0

Giải thích: Không cần đồng nào để có số tiền 0.

📈 Phân tích độ phức tạp

• Thời gian: O(S × N) với S là số tiền cần đổi, N là số loại đồng xu.
• Không gian: O(S) vì sử dụng mảng dp để lưu kết quả trung gian.

🔍 Tại sao dùng Quy hoạch động?

Với bài toán này, sử dụng quy hoạch động giúp tái sử dụng các kết quả đã tính, tránh việc phải thử lại toàn bộ tổ hợp có thể xảy ra — điều đó giúp thuật toán chạy nhanh hơn rất nhiều so với cách thử tất cả các khả năng (brute-force).