Chương trình tìm số lượng tiền cần thiết để thực hiện các thay đổi với một bộ tiền nhất định bằng Python

Giả sử chúng ta có tiền xu có mệnh giá khác nhau và tổng số tiền là bao nhiêu. Chúng ta phải xác định một hàm để tính số lượng coin ít nhất mà chúng ta cần để tạo nên số tiền đó. Khi số tiền đó không thể chứa được bằng bất kỳ sự kết hợp nào của các đồng xu, hãy trả về -1. Vì vậy, nếu đầu vào là [1,2,5] và số lượng là 64, thì đầu ra là 14. Giá trị này được hình thành bằng cách sử dụng 12 * 5 + 2 + 2 =64.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu số tiền =0, thì trả về 0
• nếu số tiền tối thiểu> số tiền, thì trả về -1
• xác định một mảng được gọi là dp, có kích thước số tiền là + 1 và điền vào mảng này với -1
• cho tôi trong mảng tiền xu trong phạm vi
  • if i> length of dp - 1, then bỏ qua phần tiếp theo, chuyển sang phần tiếp theo
  • dp [i]:=1
  • cho j trong phạm vi i + 1 thành số tiền
    • nếu dp [j - 1] =-1, thì bỏ qua phần tiếp theo, chuyển sang lần lặp tiếp theo
    • ngược lại nếu dp [j] =-1 thì dp [j]:=dp [j - i] + 1
    • nếu không thì dp [j]:=tối thiểu là dp [j] và dp [j - i] + 1
• trả lại dp [số tiền]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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],64))

Đầu vào

[1,2,5], 64

Đầu ra

14