用于硬币兑换的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 给定 N 个硬币，我们想要兑换这些硬币，使得 S 中每个值的供应量都是无限的。我们需要显示有多少种方式可以进行兑换，而不管顺序如何。

我们将使用动态规划的概念来解决问题陈述，以降低时间复杂度。

现在让我们观察下面实现中的解决方案 −

示例

# 动态方法
def count(S, m, n):
   # 基本情况
   table = [[0 for x in range(m)] for x in range(n+1)]
   # for n=0
   for i in range(m):
      table[0][i] = 1
   # 其余值以自下而上的方式填充
   for i in range(1, n+1):
      for j in range(m):
         # 包括 S[j] 的解决方案
         x = table[i - S[j]][j] if i-S[j] >= 0 else 0
         # 不包括 S[j] 的解决方案
         y = table[i][j-1] if j >= 1 else 0
         # 总计
         table[i][j] = x + y
   return table[n][m-1]
# main
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print(“Number of coins:”,end=””)
print(count(arr, m, n))