Chương trình tìm số đồng xu tối thiểu để đổi tiền với tập đồng xu cho trước bằng Python

Cho các mệnh giá đồng xu và số tiền amount. Tìm số đồng xu ít nhất để đổi tiền. Nếu không thể, trả về -1.

Ví dụ: coins = [1,2,5], amount = 64 → 14 (12×5 + 2 + 2 = 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:
   • 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, coins, amount):
        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([1, 2, 5], 64))  # Output: 14

Đầu vào

[1, 2, 5], 64

Đầu ra

14