用 Python 编写程序来找出我们可以用硬币和数量得出的不同硬币总数?

pythonserver side programmingprogramming更新于 2026/2/16 15:40:17

假设我们有一个名为硬币的值列表和另一个长度相同的名为数量的列表。第 i 个硬币的价值是 coins[i]，我们目前有 quantum[i] 个硬币。我们必须找到可以使用这些硬币的非空组获得的不同硬币总和值的数量。

因此，如果输入为 coins = [1, 2, 5] quantums = [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))