โปรแกรมหาจำนวนเหรียญที่จะถึงเป้าหมายใน Python

สมมติว่าเรามีรายการเหรียญและมูลค่าอีกจำนวนหนึ่ง เราต้องหาจำนวนชุดค่าผสมที่มียอดรวมนั้น หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขผลลัพธ์ด้วย 10^9 + 7

ดังนั้น หากการป้อนเป็นเหมือนเหรียญ =[2, 5] จำนวน =10 ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถสร้างชุดค่าผสมเหล่านี้ − [2, 2, 2, 2, 2], [5, 5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7
• dp :=รายการขนาดเท่ากับจำนวน + 1 และเติมด้วย 0
• dp[0] :=1
• สำหรับแต่ละ d ในเหรียญ ทำ
  • สำหรับฉันในช่วง 1 ถึงขนาด dp ทำ
    • ถ้า i - d>=0 แล้ว
      • dp[i] :=dp[i] + dp[i - d]
• ผลตอบแทน (องค์ประกอบสุดท้ายของ dp) mod m

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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))

อินพุต

[2, 5], 10

ผลลัพธ์

2