经典指数          
原因
2622
浏览数
0
收藏数
 

有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?

     举报   纠错  
 
切换
1 个答案

这其实也是一个Fibonacci问题

n=1时,就只有1中情况。

n=2时,有2个1分和一个2分两种。

n=3时,有f(2)+f(1)=3种。

n=4时,有f(3)+f(2)=5种。

n=5时,有f(4)+f(3)+1=9种。加1是多了一个5分可选。

6

n=10时,有f(9)+f(8)+f(5)+1。加1是多了一个10分可选。

n>10时,有f(n-1)+f(n-2)+f(n-5)+f(n-10)种情况。

 
切换
撰写答案