Đổi tiền trong Python

Cho các đồng xu với mệnh giá khác nhau và một số tiền tổng amount. Cần viết hàm tính số lượng đồng xu ít nhất để tạo ra amount đó. Nếu không thể tạo ra amount bằng bất kỳ tổ hợp nào, trả về -1. Ví dụ: coins = [1,2,5], amount = 11, đầu ra là 3 (5 + 5 + 1 = 11).

Giải pháp dùng quy hoạch động:

• Nếu amount = 0, trả về 0
• Nếu min(coins) > amount, trả về -1
• Tạo mảng dp kích thước amount + 1, khởi tạo -1
• Với mỗi đồng xu i trong coins:
  • Nếu i > amount, bỏ qua
  • dp[i] := 1
  • Với j từ i+1 đến amount:
    • Nếu dp[j-i] = -1, bỏ qua
    • Ngược lại nếu dp[j] = -1, dp[j] := dp[j-i] + 1
    • Ngược lại dp[j] := min(dp[j], dp[j-i] + 1)
• Trả về dp[amount]

Ví dụ (Python):

Xem triển khai sau để hiểu rõ hơn:

class Solution(object): 
    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], 11))

Đầu vào

[1,2,5] 11

Đầu ra

3