python多少钱

假设你手上有money这么多的钱，到货币兑换点，有面值为coins的list供你选择，money是int，coins也由int组成。问：能有多少种兑换方法？

如：有0元，有[2,5,7]可以换 ，能有0种方法换；

有5元，有[2,5]可以换，能有1种方法换；

有5元，有[]可以换，能有0种方法换；

有5元，有[1,2]可以换，能有3种方法换:(1,1,1,1,1),(1,1,1,2),(1,2,2)

验证示例

count_change(5,[1,2]) # 3

count_change(100, [5,3,7,11,2]) # 3022

count_change(1000, [5,3,7,2]) # 814044

代码（以下将先放最慢的代码，最后放快的）

这种方法最慢

def count_change(money,coins):

par = [money//i + 1 for i in coins]

f = lambda a,b:a*b

tol = reduce(f,par)

c = 0

for i in range(tol):

s = sum([coins[j]*((i//reduce(f,par[j+1:])%par[j]))

for j in range(len(coins)-1)])

s += coins[-1]*(i%par[-1])

if s == money:

c += 1

return c

这种方法模仿迷宫深度优先算法，但小于目标的实在不需要算，拖慢速度

def count_change3(money,coins):

coins.sort(reverse=True)

lenLst = len(coins)

solutions = []

subSo = []

subSo.append(coins.copy())

while subSo:

while sum([i[-1] for i in subSo]) < money:

subSo.append([i for i in coins.copy() if i >= subSo[-1][-1]])

temp = [i[-1] for i in subSo]

if sum(temp) == money:

solutions.append(temp)

subSo[-1].pop()

try:

while not subSo[-1]:

subSo.pop()

if subSo:

if subSo[-1]:

except IndexError:

continue

return len(solutions)

这种方法，利用整体思想，传参递归

def count_change(money, coins):

if money<0:

return 0

if money == 0:

return 1

if money>0 and not coins:

return count_change(money-coins[-1],coins) + count_change(money,coins[:-1])

这种方法直接建立缓存，算每种求和的换法总数

A = [1] + [0]*money

for c in coins:

A = [sum(A[:k+1][::-c]) for k in range(money+1)]

return A[-1]