当前位置: 首页 > >

python函数找钱_找钱问题?动态规划一例

发布时间:

用无限多的面值为 S = {S1, S2,? …, Sm} 的分币,表示一个特定的分值n,有多少种方法?这个就是找钱问题 (Coin Change Problem)。


比如,用 1美分 和 5 美分,表示7美分,有2种方法,第一种是1个5美分,2个1美分;第二种是7个1美分。


因为顺序对结果没有影响,即“1个5美分,2个1美分”和“2个1美分,1个5美分”是一样的,我们限定 S1 < S2 < … < Sm。用递归的方法,解法的数量 C(n, m),可以分成2类:


一类是表示方法里不需要 Sm的,另一类是表示方法里需要Sm的。如上面的例子,一类表示是需要5美分,另一类不需要。


于是,递归公式如下:


C(n, m) = C(n, m-1) + C(n-Sm, m)


Python代码:def count1(n,m):


global numCalls


numCalls += 1


global S


if n == 0:


return 1


if n < 0:


return 0


if m == 1:


return 1


return count1(n, m-1) + count1(n-S[m-1],m)


S = (1,5,10,25)


numCalls = 0


print count1(100,len(S))


print numCalls


count1()函数的运



友情链接: