python换硬币(理学院举办换硬币活动)
换硬币
作者：tiffany3344
时间限制: 1Sec 内存限制: 128MB
题目描述
理学院举办换硬币活动，假设有一个面值为N(1<=Ｎ<=10)的纸币，给定两种不同零钱：1元和2元，数目不限。如果把这张N元的纸币换成零钱，，一共有多少种不同的换法？
例如，面值为4的纸币一共有如下5种换法：
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
只有一个数N，代表纸币面值
输出一个数，代表所有不同的兑换方法的总数
4
5
N = int(input())
def dfs(N):
if(N==0):
return 1;
count1 = 0
count2 = 0
if(N-1 >= 0):
count1 = dfs(N - 1)
if(N - 2 >= 0):
count2 = dfs(N - 2)
return count1 + count2
print(dfs(N))
解的答案是:[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
我们发现规律,后一项的值等于前2项之和。
可以修改dfs()函数为:
def dfs(N):
if N == 1:
return 1
if N == 2:
return 2
return dfs(N-1)+dfs(N-2)
解法2:带记忆的背包(效率提升)
N = int(input())
#data列表记录已经算出过的值，避免重复计算
data = [0]*1001
def dfs(N):
#data为全局变量，记录下来修改过的data列表的值
global data
if(data[N] != 0):
return data[N]
if(N == 1):
return 1
if(N == 2):
return 2
# 把算出来的值添加进data列表
data[N] = dfs(N-1) + dfs(N-2)
return dfs(N-1) + dfs(N-2)
print(dfs(N))
解法3:(动态规划—快到飞起)
状态转移方程:f(n) = f(n-1) + f(n-2)
N = int(input())
def dp(N):
data = [0,1,2]
for i in range(3,N + 1):
data.append(data[i-1] + data[i-2])
return data[N]
print(dp(N))
解法4:打表(oj得分神器，专治各种不服，时间复杂度O(1))
N = int(input())
data = [0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711]
print(data[N])
作者：tiffany3344
