硬币和
|
英镑$\unicode{xA3}$和便士p是英国的基本货币单位。目前流通的硬币共有八种类面值：
$$1p, 2p, 5p, 10p, 20p, 50p, \unicode{xA3}1(=100p), \unicode{xA3}2(=200p)$$
凑成$\unicode{xA3}2$的一种做法是
$$1\times \unicode{xA3}1+ 1\times 50p + 2 \times 20 p+1\times 5p+ 1\times 2p+3\times 1p$$
若不限制硬币数量，则凑成$\unicode{xA3}2$的做法共有几种？
|
本题难度:
|
解答
|
设目标价值是T便士，第一枚硬币的价值是c便士，那么只需再考察凑出$T-c$便士的方法总数。令c取遍所有可能的值后相加就是凑成T便士的方法总数，递归计算即得结果$73682$。
coins=[1,2,5,10,20,50,100,200]
nums=[1]+[0]*200
for i in range(8):
for j in range(coins[i], len(nums)):
nums[j]+=nums[j-coins[i]]
print nums[-1]
|
| |
