Chương trình tìm số lượng kết hợp các loại tiền để đạt được mục tiêu bằng Python

Giả sử chúng ta có một danh sách các đồng xu và một số lượng giá trị khác, chúng ta phải tìm số lượng kết hợp có tổng đó thành số tiền. Nếu câu trả lời là rất lớn, thì hãy sửa đổi kết quả bằng 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như xu =[2, 5] số tiền =10, thì đầu ra sẽ là 2, vì chúng ta có thể thực hiện các kết hợp này - [2, 2, 2, 2, 2], [5, 5]

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

• m:=10 ^ 9 + 7
• dp:=một danh sách có kích thước giống như số tiền + 1 và điền nó bằng 0
• dp [0]:=1
• đối với mỗi d tính bằng xu, hãy thực hiện
  • đối với tôi trong phạm vi từ 1 đến kích thước là dp, hãy thực hiện
    • nếu i - d> =0, thì
      • dp [i]:=dp [i] + dp [i - d]
• return (phần tử cuối cùng của dp) mod m

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

Ví dụ

class Solution:
   def solve(self, coins, amount):
      dp = [0] * (amount + 1)
      dp[0] = 1
      for d in coins:
         for i in range(1, len(dp)):
            if i - d >= 0:
               dp[i] += dp[i - d]
      return dp[-1] % (10 ** 9 + 7)
ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

Đầu vào

[2, 5], 10

Đầu ra

2