Python程序：计算使用不同硬币组合可以得到的不同金额数

假设我们有一个名为coins的数值列表和另一个名为quantities的相同长度的列表。第i枚硬币的值为coins[i]，我们目前有quantities[i]个第i枚硬币。我们需要找到使用这些硬币的非空组合可以得到的不同金额数。

例如，如果输入为coins = [1, 2, 5]，quantities = [1, 2, 1]，则输出为10，因为我们可以得到以下不同的金额：[1] = 1，[2] = 2，[1,2] = 3，[2,2] = 4，[5] = 5，[1,5] = 6，[2,5] = 7，[1,2,5] = 8，[2,2,5] = 9，[1,2,2,5] = 10。

为了解决这个问题，我们将遵循以下步骤

定义一个函数rec()。它将接收i和res作为参数。

if i is same as size of coins , then
   return
for k in range 0 to quantities[i] + 1, do
   cur := res + k * coins[i]
   insert cur into fres
   rec(i + 1, cur)
From the main method, do the following:
fres := a new set
rec(0, 0)
return size of fres - 1

示例

 在线演示

class Solution:
   def solve(self, coins, quantities):
      def rec(i, res):
         if i == len(coins):
            return
         for k in range(0, quantities[i] + 1):
            cur = res + k * coins[i]
            fres.add(cur)
            rec(i + 1, cur)

      fres = set()
      rec(0, 0)
      return len(fres) - 1

ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))

输入

[1, 2, 5], [1, 2, 1]

输出

10

更新于：2020年11月10日

521 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告