Chương trình tìm số đồng xu tối thiểu để đổi tiền (mệnh giá cố định) bằng Python

Cho mệnh giá đồng xu cố định [1, 5, 10, 25] và số tiền amount. Tìm số đồng xu ít nhất để đổi tiền.

Ví dụ: amount = 64 → 7 (25+25+10+1+1+1+1 = 64).

Quy trình giải quyết (Dynamic Programming)

1. Nếu amount == 0, trả về 0.
2. Nếu mệnh giá nhỏ nhất > amount, trả về -1.
3. Tạo mảng dp kích thước amount+1 khởi tạo -1.
4. Với mỗi mệnh giá i trong [1,5,10,25]:
   • Nếu i vượt quá kích thước dp, bỏ qua.
   • dp[i] = 1.
   • Với j từ i+1 đến amount:
     • Nếu dp[j-i] == -1, bỏ qua.
     • Nếu dp[j] == -1, gán dp[j] = dp[j-i] + 1.
     • Ngược lại dp[j] = min(dp[j], dp[j-i] + 1).
5. Trả về dp[amount].

Ví dụ mã nguồn

class Solution:
    def coinChange(self, amount):
        coins = [1, 5, 10, 25]
        if amount == 0:
            return 0
        if min(coins) > amount:
            return -1
        dp = [-1 for i in range(0, amount + 1)]
        for i in coins:
            if i > len(dp) - 1:
                continue
            dp[i] = 1
            for j in range(i + 1, amount + 1):
                if dp[j - i] == -1:
                    continue
                elif dp[j] == -1:
                    dp[j] = dp[j - i] + 1
                else:
                    dp[j] = min(dp[j], dp[j - i] + 1)
        return dp[amount]

ob1 = Solution()
print(ob1.coinChange(64))  # Output: 7

Đầu vào

64

Đầu ra

7