题目描述

考虑仅用1分、5分、10分、25分和50分这5种硬币支付某一个给定的金额。例如需要支付11分钱，有一个1分和一个10分、一个1分和两个5分、六个1分和一个5分、十一个1分这4种方式。

请写一个程序，计算一个给定的金额有几种支付方式。

注：假定支付0元有1种方式。

输入描述:

输入包含多组数据。 每组数据包含一个正整数n（1≤n≤10000），即需要支付的金额。

输出描述:

对应每一组数据，输出一个正整数，表示替换方式的种数。

示例1

输入

11 26

输出

4 13 思路：使用动态规划来做，dp[i][j]表示前i种零钱换总金额为j的方法种数： 如果第i种货币参与换算，那么第i中货币可能有0个，1个，2个，3个...k个，dp[i][j] = dp[i-1][j] + dp[i-1][j-1*money[i]] + dp[i-1][j-2*money[i]] +...+ dp[i-1][j-k*money[i]],其中k*money[i] <= j 　　递归递推公式： 　　　　dp[i][j] = dp[i-1][j] + dp[i-1][j-1*money[i]] + dp[i-1][j-2*money[i]] +...+ dp[i-1][j-k*money[i]],其中k*money[i] <= j 　　那么,将j = j - money[i]进行替换，则 　　　　dp[i][j-money[i]] = dp[i-1][j-1*money[i]] + dp[i-1][j-2*money[i]] +...+ dp[i-1][j-k*money[i]],其中k*money[i] <= j 　　将上面两个等式进行合并，那么： 　　　　dp[i][j] = dp[i-1][j] + dp[i][j-money[i]]

如果第i种货币不参与换算，那么: 　　dp[i][j] = dp[i-1][j] 最后代码实现如下：

money=[1,5,10,25,50]dp = []def getCount(n):    for i in xrange(5):        dp.append((n+1)*[0])        dp[i][0] = 1    for i in xrange(n+1):        dp[0][i] = 1    for i in xrange(1,5):        for j in xrange(1,n+1):            if j < money[i]:                dp[i][j] = dp[i-1][j]            else:                dp[i][j] = dp[i-1][j] + dp[i][j-money[i]]getCount(10000)while True:    n = int(raw_input())    if n:        print dp[4][n]    else:        break

优化：二维数组每次都是只用到了2个数，那么应该可以用一维数组进行优化，它的表示是：dp[i]：总金额为i的换零钱的方法数目。

dp[0] = 1,由题目意思可得

dp[i] = dp[i-money[0]] + dp[i-money[1]] + dp[i-money[2]] + dp[i-money[3]] + dp[i-money[4]],其中i >= money[j],j=0..4

意思是，第i种状态，由前面几种状态转化而来的，类似于跳台阶。

代码如下：

money=[1,5,10,25,50]dp = [0] * 10001dp[0] = 1def getCount(n):    for i in xrange(5):        j = money[i]        while j < n:            dp[j] += dp[j-money[i]]            j = j + 1getCount(10001)while True:    try:        n = int(raw_input())        print dp[n]    except:        break