有1分,2分,5分,10分四种硬币,每种硬币数量无限,给定n分钱,求有多少种组合可以组合成n分钱?
这其实也是一个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)种情况。
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)种情况。